题意：
给一个结点数为n的无向图，边x,y的值为l表示x,y之间有l张多米诺骨牌，现在推倒点1处的多米诺骨牌，每张多米诺骨牌倒下要1s,求最后一张多米诺骨牌倒下时的时间。
思路；
先求单源最短路，再枚举最后一张到的位置，注意要枚举倒在两点之间的情况。
代码：
//poj 1135
//sepNINE
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int maxN=512;int g[maxN][maxN];
int inq[maxN];
int dis[maxN];
int n,m;void spfa()
{int i;queue<int> Q;memset(inq,0,sizeof(inq));for(i=1;i<=n;++i) dis[i]=INT_MAX; inq[1]=1;dis[1]=0;Q.push(1);while(!Q.empty()){int u=Q.front();Q.pop();inq[u]=0;for(int i=1;i<=n;++i)if(g[u][i]!=0&&dis[u]+g[u][i]<dis[i]){dis[i]=dis[u]+g[u][i];if(!inq[i]){inq[i]=1;Q.push(i);}} }
}int main()
{int cases=0;while(scanf("%d%d",&n,&m)==2&&n){memset(g,0,sizeof(g));int i,j,a,b,c;while(m--){scanf("%d%d%d",&a,&b,&c); g[a][b]=g[b][a]=c;}spfa();double ans1=-1.0,ans2=-1.0;int p,q,r;for(i=1;i<=n;++i) if(ans1<dis[i]*1.0){ans1=dis[i]*1.0;p=i;}for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(i!=j&&dis[i]<=dis[j]&&g[i][j]!=0)if(ans2<(dis[i]+g[i][j]+dis[j])*1.0/2){ans2=(dis[i]+g[i][j]+dis[j])*1.0/2;q=i;r=j; }if(ans1>ans2||fabs(ans1-ans2)<1e-6)printf("System #%d\nThe last domino falls after %.1lf seconds, at key domino %d.\n\n",++cases,ans1,p);elseprintf("System #%d\nThe last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n",++cases,ans2,min(q,r),max(q,r));} return 0;
}