Posted on 2008-06-07 22:32
superman 阅读(474)
评论(1) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1298 C++ 00:00.01 1824K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 int n, m;
8 int map[500][500];
9
10 void spfa(int s, int d[])
11 {
12 for(int i = 1; i <= n; i++)
13 d[i] = INT_MAX;
14 d[1] = 0;
15
16 queue <int> q;
17 q.push(1);
18
19 while(q.empty() == false)
20 {
21 int cur = q.front(); q.pop();
22 for(int i = 1; i <= n; i++)
23 if(cur != i && map[cur][i] != INT_MAX && d[cur] + map[cur][i] < d[i])
24 {
25 d[i] = d[cur] + map[cur][i];
26 q.push(i);
27 }
28 }
29 }
30
31 int main()
32 {
33 cout.setf(ios_base::showpoint);
34 cout.setf(ios_base::fixed);
35 cout.precision(1);
36
37 int cnt = 1;
38 while(cin >> n >> m)
39 {
40 if(n == 0 && m == 0)
41 break;
42
43 for(int i = 1; i <= n; i++)
44 for(int j = 1; j <= n; j++)
45 map[i][j] = INT_MAX;
46
47 int s, t, l;
48 for(int i = 0; i < m; i++)
49 {
50 cin >> s >> t >> l;
51 map[s][t] = map[t][s] = l;
52 }
53
54 int d[500];
55 spfa(1, d);
56
57 double ans = 0; int idx = 1;
58 for(int i = 2; i <= n; i++)
59 if(d[i] > ans)
60 {
61 ans = d[i];
62 idx = i;
63 }
64 int x = 0, y = 0;
65 for(int i = 1; i <= n; i++)
66 for(int j = i + 1; j <= n; j++)
67 if(map[i][j] != INT_MAX)
68 {
69 double k = (map[i][j] - abs(d[i] - d[j])) * 0.5 + max(d[i], d[j]);
70 if(ans < k)
71 {
72 ans = k;
73 x = i, y = j;
74 }
75 }
76
77 cout << "System #" << cnt++ << endl
78 << "The last domino falls after " << ans << " seconds, ";
79 if(x == 0 && y == 0)
80 cout << "at key domino " << idx << '.' << endl;
81 else
82 cout << "between key dominoes " << x << " and " << y << '.' << endl;
83 cout << endl;
84 }
85
86 return 0;
87 }
88