// UVa 10000 - Longest Paths #include <iostream> #include <stdio.h> #include <queue> #include <string.h> using namespace std; int main() { int n; int t = 0; while ((cin >> n) && n) { t++; int s; cin >> s; bool lnk[101][101]; memset(lnk, false, sizeof(lnk)); int parents[101]; memset(parents, 0, sizeof(parents)); int p, o; while (cin >> p >> o && p && o) { lnk[p][o] = true; parents[o]++; } int lvl[101]; memset(lvl, 255, sizeof(lvl)); queue<int> q; q.push(s); lvl[s] = 0; int sol = s; while (!q.empty()) { int m = q.front(); q.pop(); for (int i = 1; i <= n; i++) if (lnk[m][i]) { parents[i]--; if (lvl[i] < lvl[m] + 1) { lvl[i] = lvl[m] + 1; q.push(i); if (lvl[sol] < lvl[i] || lvl[sol] == lvl[i] && i < sol) sol = i; } } } printf("Case %d: The longest path from ", t); printf("%d has length %d, finishing at %d.\n\n", s, lvl[sol], sol); } return 0; }
Saturday, June 13, 2015
UVa 10000 - Longest Paths
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment