-
Notifications
You must be signed in to change notification settings - Fork 2
/
10000.cpp
82 lines (72 loc) · 1.18 KB
/
10000.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define maxn 102
struct ss {
int u, cost;
};
queue<ss>Q;
vector<int>link[maxn];
int N, S, maxx, res;
int Cost[maxn];
void BFS() {
ss t, d;
int i, v;
t.u = S;
t.cost = maxx = res = 0;
Q.push(t);
while(!Q.empty()) {
t = Q.front();
Q.pop();
for(i = 0; i<link[t.u].size(); i++) {
v = link[t.u][i];
if(Cost[v] < (t.cost + 1)) {
Cost[v] = t.cost + 1;
d.u = v;
d.cost = Cost[v];
Q.push(d);
if(maxx == d.cost && v < res){
res = v;
}
if(maxx < d.cost){
maxx = d.cost;
res = v;
}
}
}
}
cout<<"The longest path from "<<S<<" has length ";
cout<<maxx<<", finishing at "<<res<<".\n";
}
void Cal() {
if(N == 1) {
cout<<"The longest path from 1 has length 0, finishing at 1.\n";
return;
}
BFS();
}
void Free() {
int i;
for(i = 1; i<= N; i++) {
Cost[i] = 0;
link[i].clear();
}
}
int main() {
int u, v, i, k = 1;
//freopen("c:\\h.txt","r",stdin);
while(cin>>N && N) {
cin>>S;
for(i = 0; i<1000000; i++) {
cin>>u>>v;
if(!u && !v) break;
link[u].push_back(v);
}
cout<<"Case "<<k++<<": ";
Cal();
Free();
cout<<endl;
}
return 0;
}