题目：http://poj.org/problem?id=1135
只是求以1为起点的最短路罢了。稍稍判断一下在边上的情况。
多亏提醒：毒数据——n==1！一定要dis [ k ] >= ans！！！
注意输出格式（换行）。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int n,m,head[505],xnt,x,y,T; int hp[5005],cnt,k1,k2; ll dis[505],z; double ans; bool vis[505]; struct Edge{ int next,to; ll w; Edge(int a=0,int b=0,ll c=0):next(a),to(b),w(c) {} }edge[500005]; ll abss(ll k) { if(k<0)k=-k; return k; } void push(int k) { hp[++cnt]=k; int now=cnt; while(now>1) { int tp=(now>>1); if(dis[hp[now]]<dis[hp[tp]])swap(hp[now],hp[tp]); else break; now=tp; } } int del() { int res=hp[1]; hp[1]=hp[cnt--]; int now=1; while((now<<1)<=cnt) { int tp=(now<<1); if(tp<cnt&&dis[hp[tp+1]]<dis[hp[tp]])tp++; if(dis[hp[tp]]<dis[hp[now]])swap(hp[tp],hp[now]); else break; now=tp; } return res; } int main() { while(++T) { scanf("%d%d",&n,&m); if(!n&&!m)return 0; memset(dis,11,sizeof dis); memset(head,0,sizeof head); memset(vis,0,sizeof vis); xnt=0;ans=0;k1=0;k2=0; for(int i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&z); edge[++xnt]=Edge(head[x],y,z);head[x]=xnt; edge[++xnt]=Edge(head[y],x,z);head[y]=xnt; } dis[1]=0;push(1); while(cnt) { int k=del(); while(cnt&&vis[k])k=del(); if(vis[k])break; vis[k]=1; if(dis[k]>=ans)////////// { ans=dis[k];k1=k; } for(int i=head[k],v;i;i=edge[i].next) if(!vis[v=edge[i].to]&&dis[k]+edge[i].w<dis[v]) { dis[v]=dis[k]+edge[i].w; push(v); } } double c=0; for(int i=1;i<=n;i++) for(int j=head[i],v;j;j=edge[j].next) if(abss(dis[i]-dis[v=edge[j].to])<edge[j].w&& (c=max(dis[i],dis[v])+(double)(edge[j].w-abss(dis[i]-dis[v]))/2)>ans) { ans=c;k1=min(i,v);k2=max(i,v); } printf("System #%d ",T); if(!k2) printf("The last domino falls after %.1lf seconds, at key domino %d. ",ans,k1); else printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d. ",ans,k1,k2); } }