UVa 11792 - Krochanska is Here!

// UVa 11792 - Krochanska is Here!

#include <iostream>
#include <string.h>
using namespace std;

int main() {

	int cases;
	for (cin >> cases; cases; cases--) {

		int n, s;
		int count[10001];
		int m = 1;
		int imp[10001];
		int idx[101];
		memset(imp, 0, sizeof(imp));
		memset(count, 0, sizeof(count));
		int train[100][10001];
		// input and figure out important stations
		cin >> n >> s;
		for (int i = 0; i < s; i++) {
			int j = 0;
			cin >> train[i][j];
			while (train[i][j] != 0) {
				count[train[i][j]]++;
				if (count[train[i][j]] == 2) {
					imp[train[i][j]] = m;
					idx[m] = train[i][j];
					m++;
				}
				j++;
				cin >> train[i][j];
			}
		}

		unsigned long long int lnk[101][101];
		memset(lnk, 255, sizeof(lnk));
		unsigned long long int path[101][101];
		memset(path, 255, sizeof(path));
		unsigned long long int oo = path[0][0];
		// construct graph with only important stations
		for (int i = 0; i < s; i++) {
			int j = 0;
			while (train[i][j] != 0) {
				int a = imp[train[i][j]];
				if (a) {
					for (int k = 0; k <= j; k++) {
						int b = imp[train[i][k]];
						if (b) {
							if (j - k < lnk[a][b]) {
								lnk[a][b] = j - k;
								lnk[b][a] = j - k;
								path[a][b] = j - k;
								path[b][a] = j - k;
							}
						}
					}
				}
				j++;
			}
		}

		// all-to-all shortest paths
		for (int k = 1; k < m; k++)
			for (int i = 1; i < m; i++)
				for (int j = 1; j < m; j++)
					if (path[i][j] > path[i][k] + path[k][j])
						path[i][j] = path[i][k] + path[k][j];

		unsigned long long int sol = oo;
		int ss;
		// where is Krochanska?
		for (int i = 1; i < m; i++) {
			unsigned long long int sum = 0;
			for (int j = 1; j < m; j++) {
				sum += path[i][j];
			}
			if (sum < sol || (sum == sol && idx[i] < ss)) {
				sol = sum;
				ss = idx[i];
			}
		}

		// output
		cout << "Krochanska is in: " << ss << endl;

	}

	return 0;
}