#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000
#define INF 1000000
int edge[MAXN][MAXN];//存储数据的数组
int n;//关键牌数
int kcase=1;
int Time[MAXN];//存放关键牌的时间
int S[MAXN];//存放已加入顶点的集合
void solve_caes(int n)//全局变量n是不是需要传过来
{
// printf("n=%d\n",n);
int u,i,j,k;
for(i=1;i<=n;i++)
{
Time[i]=edge[1][i];//第一行的时间
S[i]=0;//表示全都没选中
// printf("Time[%d]=%d\n",i,Time[i]);
}
Time[1]=0;S[1]=1;//将第一个元素分别加入S[],Time[]中
for(i=1;i<n;i++)//Dijkstra算法核心,确定从1到n-1条最短路径
{
int min=INF;
u=1;
for(j=1;j<=n;j++)
{
if(!S[j] && min>Time[j])//从没有加入S[]集合并权值最小中查找,
//并标记;
{
u=j;
min=Time[j];
// printf("u=%d\n",u);
}
}
S[u]=1;//通过上面的查找将U加入到集合当中去,那么Time[u]在哪里求的呢
for(k=1;k<=n;k++)//修改两个数组的元素
{
if(!S[k] && edge[u][k]<INF && Time[u]+edge[u][k]<Time[k])
{
Time[k]=Time[u]+edge[u][k];
}
}
}
double maxtime1=-INF;//因为在下面要找最大的Time[i],
//比较的话只能用大于一个比谁都小的数字了
int pos;//定义倒下的关键牌时间及其位置
// printf("%lf\n",maxtime1);
for(i=1;i<=n;i++)
{
// printf("Time[%d]=%d\n",i,Time[i]);
if(Time[i]>maxtime1)
{
maxtime1=Time[i];
pos=i;//记录下此时的pos
}
}
// printf("i=%d\nmaxtime1=%lf\n",pos,maxtime1);
double maxtime2=-INF,t;//记录每一行普通牌中间位置倒下的时间最大值
//及其位置
int pos1,pos2;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t=(Time[i]+Time[j]+edge[i][j])/2.0;//肯定能取整
if(edge[i][j]<INF && t>maxtime2)
{
maxtime2=t;
pos1=i;
pos2=j;
//printf("kkkkk\n");
}
}
//printf("qqqqqq\n");
}
printf("System #%d\n",kcase++);
printf("The last domino falls after ");
if(maxtime1>=maxtime2)
printf("%0.1lf seconds, at key domino %d.\n\n",maxtime1,pos);
else
printf("%0.1lf seconds, between key dominoes %d and %d.\n\n",maxtime2,pos1,pos2);
}
int main()
{
//freopen("in.txt","r",stdin);
int i,j,m,v1,v2,t,tmp;
while(1)
{
cin>>n>>m;
if(n==0 && m==0)
break;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
edge[i][j]=INF;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&v1,&v2,&t);
edge[v2][v1]=edge[v1][v2]=t;
}
/* for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
printf("%d\t",edge[i][j]);
}*/
solve_caes(n);
}
return 0;
}原文：http://blog.csdn.net/yuzibo747/article/details/19297477