这道题目的意思大致是给你n个骨牌，以及某些骨牌之间的边，这些边的权值代表，从这条边的某一端（某一骨牌）开始倒，一直倒到该边的终点（该边的另一个骨牌）所需的时间，然后题目的求的是，从编号为1的骨牌开始倒（注意，某一个骨牌倒的时候，连同与其相邻的边都同时开始往外面倒），求最后倒的骨牌的位置（在某两个骨牌之间或者是刚给你的n个骨牌的其中一个）,并输出时间.....首先求骨牌1到其他所有关键骨牌的最短路（Dijkstra），即为每个关键骨牌倒的时间，再枚举所有边，对于骨牌i和骨牌j之间的边，全部倒下的时间为(dist[i] + dist[j] + dom[i][j])/2，比较此值与最短路中的最大值，大者即为所求。
1 #include<iostream>
2 #include<limits>
3
4 using namespace std;
5
6 const int maxN = 500;
7 const int INF = numeric_limits<int>::max();
8
9 int dom[maxN][maxN];
10
11 int dist[maxN];
12
13 //Dijkstra 算法求1号骨牌到其他关键牌的最短路
14 void Dijkstra(int n, int v)
15 {
16 bool s[maxN];
17 for(int i=1;i<=n;i++)
18 {
19 dist[i]=dom[v][i];
20 s[i]=false;
21 }
22
23 dist[v]=0;
24 s[v]=true;
25
26 for(int i=1;i<n;i++)
27 {
28 int temp = INF;
29 int u = v;
30 for(int j=1;j<=n;j++)
31 {
32 if((!s[j] && dist[j] < temp))
33 {
34 u = j;
35 temp = dist[j];
36 }
37 }
38 s[u] = true;
39
40 for(int j=1; j<=n; j++)
41 {
42 if((!s[j] && dom[u][j] != INF))
43 {
44 int newDist = dist[u] + dom[u][j];
45 if(newDist < dist[j])
46 {
47 dist[j] = newDist;
48 }
49 }
50 }
51 }
52 }
53
54 int main(void)
55 {
56 int n,m;
57 int a,b;
58 int maxLen;
59 double maxTime;
60
61 int atKey[2];
62
63 int i,j;
64
65 int NO = 1;
66 cin>>n>>m;
67 while(!(n==0 && m==0))
68 {
69 for(i=1;i<=n;i++) // 初始化
70 {
71 for(j=1;j<=n;j++)
72 {
73 dom[i][j] = INF;
74 }
75 }
76
77 for(i=0;i<m;i++)
78 {
79 cin>>a>>b;
80 cin>>dom[a][b];
81 dom[b][a]=dom[a][b];
82 }
83
84 Dijkstra(n,1);
85
86 maxLen = dist[1];
87 atKey[0] = 1;
88 for(i=2; i<=n; i++)
89 {
90 if(dist[i] > maxLen)
91 {
92 maxLen = dist[i];
93 atKey[0] = i;
94 }
95 }
96 atKey[1] = 0;
97
98 maxTime = (double)maxLen;
99 double t;
100 for(i=1; i<=n; i++) //枚举每条边
101 {
102 for(j=i+1; j<=n; j++)
103 {
104 if(dom[i][j] != INF)
105 {
106 t=(dist[i]+dist[j]+dom[i][j])/2.0;
107 if( t > maxTime )
108 {
109 maxTime = t;
110 atKey[0] = i;
111 atKey[1] = j;
112 }
113 }
114 }
115 }
116 cout.setf(ios::fixed);
117 cout.precision(1);
118 cout<<"System #"<<NO++<<endl;
119 cout<<"The last domino falls after "<<maxTime<<" seconds, ";
120 if(atKey[1] == 0)
121 {
122 cout<<"at key domino "<<atKey[0]<<"."<<endl;
123 }
124 else
125 {
126 cout<<"between key dominoes "<<atKey[0]<<" and "<<atKey[1]<<"."<<endl;
127 }
128 cout<<endl;
129
130 cin>>n>>m;
131 }
132 return 0;
133 }