BeiyouOJ-272。ネットワークコア

Beiyou Oj 272 Network Core

トピックの説明

無向ネットワークGが与えられると、N個のノード（1からN）、M個のエッジ、およびネットワークのコアがあります。

ネットワークのコア：ネットワーク内の他のノードまでの距離の合計が最小であり、それらの間の距離は、接続されていない2つのポイントの場合はNであり、複数のセットがある場合は出力数が最小のノードです。ソリューション

入力

最初の行は、テストデータのグループの数を表す整数Tです（<26)

テストデータの各セットについて：

最初の行には2つの整数N、Mがあり、N点M辺を表します

次のM行、2つの整数u、v（<=N) per line, indicate that there is a side with a distance between points u and v, and there will be no repeated edges between any two points.

出力

出力ネットワークコア

サンプル入力

2 3 3 1 2 1 3 2 3 4 2 1 2 2 3

サンプル出力

1 2

コード

#include using namespace std / / Floyd algorithm, the node of the graph below 100 can be considered int main() { int T,a[55][55],M,N,x,y cin>>T while(T--) { cin>>N>>M / / Adjacency matrix storage For(int i=1 i<=N i++) { // The initial initialization of the graph is unreachable for(int j=1 j<=N j++) { a[i][j]=N } } //Undirected graph For(int i=1 i>x>>y a[x][y]=1 a[y][x]=1 } //Floyd algorithm body For(int k=1 k<=N k++) { //Update the adjacency matrix with k node as the intermediate node for(int i=1 i<=N i++) { for(int j=1 j<=N j++) { If(a[i][k]==N||a[k][j]==N){ //If the loop is unreachable, continue the loop and do not continue executing the loop body statement continue } if(a[i][k]+a[k][j]