백준 1389번 C++

#include <iostream>

#include <cstring>

using namespace std;

const int MAX = 987654321;

const int arr = 100;

int n, m;

int graph[arr][arr];

void floyd() {

for (int k = 1; k <= n; k++) {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (i == j)

continue;

else if (graph[i][k] != 0 && graph[k][j] != 0) {

if (graph[i][j] > graph[i][k] + graph[j][k]) {

graph[i][j] = graph[i][k] + graph[j][k];

}

}

}

}

}

}

int main(void) {

cin >> n >> m;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (i == j)

graph[i][j] = 0;

else

graph[i][j] = MAX;

}

}

for (int i = 0; i < m ; i++) {

int x, y;

cin >> x >> y;

graph[x][y] = 1;

graph[y][x] = 1;

}

floyd();

int ans;

int shortest = 987654321;

for (int i = 1; i <= n; i++) {

int counts = 0;

for (int j = 1; j <= n; j++) {

counts += graph[i][j];

}

if (counts < shortest) {

shortest = counts;

ans = i;

}

}

cout << ans;

}