題目連結
題目大意：
第一行輸入給有n張骨牌和m條edge。下面m行輸入為a b l，ab為兩邊骨牌id，l為edge長度。問從第一張開始推，最後倒下的地方。若為骨牌，輸出骨牌id；若為edge，輸出兩邊骨牌id；若edge與骨牌同時，以骨牌優先。
解題思路：
用adjecency matrix紀錄graph。跑一次Dijkstra，各點的d就是他們的倒下時間。接下來算每條edge的倒下時間，求最大的；與最大d做比較，輸出。
Code
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include < iostream>#include < cstdio>using namespace std;int adj_matrix[500][500];int d[500], Q[500];int system_count, n;void init(){ for (int i=1; i<=n; i++){ Q[i] = 1; d[i] = -1; for (int j=1; j<=n; j++) adj_matrix[i][j] = -1; } d[1] = 0;}int find_min_d(){ int min_d = 10000000, node = 1; for (int i=2; i<=n; i++){ if (d[i]< min_d && Q[i]==1 && d[i]!=-1){ min_d = d[i]; node = i; } } return node;}void relax(int u, int v){ if((d[v]>d[u]+adj_matrix[u][v]) || d[v]==-1) d[v] = d[u]+adj_matrix[u][v];}void dijkstra(){ for (int i=1; i<=n; i++){ int u = find_min_d(); Q[u] = 0; for (int v=1; v<=n; v++){ if (adj_matrix[u][v] != -1) relax(u, v); } } }void compute_print(){ double max_fall_time = 0, tmp_fall_time, big, small; int n1=0, n2=0; for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++){ if (adj_matrix[i][j]!=-1){ if(d[i]>=d[j]){ big = d[i]; small = d[j]; } else{ big = d[j]; small = d[i]; } tmp_fall_time = (adj_matrix[i][j]-(big-small))/2 + big; if (tmp_fall_time > max_fall_time){ max_fall_time = tmp_fall_time; if (i< j) n1=i, n2=j; else n1=j, n2=i; } } } } double max_d = -1; int node=0; for (int i=1; i<=n; i++){ if (d[i] > max_d){ max_d = d[i]; node = i; } } printf("System #%d\n", system_count++); if (max_d >= max_fall_time) printf("The last domino falls after %.1f seconds, at key domino %d.\n\n", max_d, node); else printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n", max_fall_time, n1,n2);}int main(){ int m, a, b, l; system_count = 1; while (true){ scanf("%d %d", &n, &m); if (n==0) break; init(); while (m--){ scanf("%d %d %d", &a, &b, &l); adj_matrix[a][b] = adj_matrix[b][a] = l; } dijkstra(); compute_print(); } return 0;} |
