Poj 1135 Domino Effect(Dijkstra)
题目描述：
你知道多米诺骨牌除了用来玩多米诺骨牌游戏外，还有其他用途吗？多米诺骨牌游戏：取一
些多米诺骨牌，竖着排成连续的一行，两张骨牌之间只有很短的空隙。如果排列得很好，当你推
倒第1 张骨牌，会使其他骨牌连续地倒下（这就是短语“多米诺效应”的由来）。
然而当骨牌数量很少时，这种玩法就没多大意思了，所以一些人在80 年代早期开创了另一个
极端的多米诺骨牌游戏：用上百万张不同颜色、不同材料的骨牌拼成一幅复杂的图案。他们开创
了一种流行的艺术。在这种骨牌游戏中，通常有多行骨牌同时倒下。
你的任务是编写程序，给定这样的多米诺骨牌游戏，计算最后倒下的是哪一张骨牌、在什么
时间倒下。这些多米诺骨牌游戏包含一些“关键牌”，他们之间由一行普通骨牌连接。当一张关键
牌倒下时，连接这张关键牌的所有行都开始倒下。当倒下的行到达其他还没倒下的关键骨牌时，
则这些关键骨牌也开始倒下，同样也使得连接到它的所有行开始倒下。每一行骨牌可以从两个端
点中的任何一张关键牌开始倒下，甚至两个端点的关键牌都可以分别倒下，在这种情形下，该行
最后倒下的骨牌为中间的某张骨牌。假定骨牌倒下的速度一致。
输入描述：
输入文件包含多个测试数据，每个测试数据描述了一个多米诺骨牌游戏。每个测试数据的第
1 行为两个整数：n 和m，n 表示关键牌的数目，1≤n<500；m 表示这n 张牌之间用m 行普通骨
牌连接。n 张关键牌的编号为1～n。每两张关键牌之间至多有一行普通牌，并且多米诺骨牌图案
是连通的，也就是说从一张骨牌可以通过一系列的行连接到其他每张骨牌。
接下来有m 行，每行为3 个整数：a、b 和t，表示第a 张关键牌和第b 张关键牌之间有一行
普通牌连接，这一行从一端倒向另一端需要t 秒。每个多米诺骨牌游戏都是从推倒第1 张关键牌
开始的。
输入文件最后一行为n = m = 0，表示输入结束。
输出描述：
对输入文件中的每个测试数据，首先输出一行"System #k"，其中k 为测试数据的序号；然后
再输出一行，首先是最后一块骨牌倒下的时间，精确到小数点后一位有效数字，然后是最后倒下
骨牌的位置，这张最后倒下的骨牌要么是关键牌，要么是两张关键牌之间的某张普通牌。输出格
式如样例输出所示。如果存在多个解，则输出任意一个。每个测试数据的输出之后输出一个空行。
样例输入：
2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
0 0
System #1
The last domino falls after 27.0 seconds, at key domino 2.
样例输出：
System #2
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.
算是模版Dijkstra题目了,多了判断哪种最优解的情况。
a) 先计算每一张关键牌倒下的dist[i]。这需要利用Dijkstra 算法求第1 张关键牌到其他每
张关键牌的最短路径。然后取dist[i]的最大值，设为max1。
b) 计算每一行完全倒下的时间。设每一行的两端的关键牌为i 和j，则这一行完全倒下的时
间为(dist[i] + dist[j] +
edge[i][j])/2.0，其中edge[i][j]为连接第i、j 两张关键牌的行倒下
所花的时间。取所有行完全倒下时间的最大值，设为max2。
c) 如果max2 > max1，则是第②种情形；否则是第①种情形。
[cpp]
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAX 600
#define INF 0x7FFFFFFF
# define eps 1e-5
using namespace std;
int n,m;
int edge[MAX][MAX],visit[MAX],dist[MAX];//边的信息，访问，最短距离
void dijkstra(int u0)
{
int i,j,v;
for(i=1; i<=n; i++)//初始化
{
dist[i] = edge[u0][i];
}
visit[u0] = 1;
for(j=0; j<n-1; j++)
{
int min = INF;
for(i=1; i<=n; i++)
{
if(!visit[i] && min > dist[i])
{
min = dist[i];
v = i;
}
}
visit[v] = 1;//点v与源点同一集合
for(i=1; i<=n; i++)//随着新的顶点加入，更新dist值
{
if(!visit[i] && edge[v][i] < INF && edge[v][i] + dist[v] < dist[i])
dist[i] = edge[v][i] + dist[v];
}
}
}
int main()
{
int i,j,a,b,c,tt = 1;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0)
break;
for(i=1; i<=n; i++)//初始化
for(j=1; j<=n; j++)
{
if(i == j)
edge[i][j] = 0;
else
edge[i][j] = INF;
}
for(i=0; i<m; i++)//构图
{
scanf("%d%d%d",&a,&b,&c);
edge[a][b] = c;
edge[b][a] = c;
}
memset(visit,0,sizeof(visit));
dijkstra(1);//求出1到所有定点最短路
double max1 = -10000000;
int index;
for(i=1; i<=n; i++)//情况a
{
if(max1 < dist[i])
{
max1 = dist[i]*1.0;
index = i;
&nbs
补充：软件开发 , C++ ,
