题目:http://poj.org/problem?id=1135
先在图中跑一遍最短路,最后倒的牌可能是dis值最大的点,也可能是在dis值最大的点所连的边上,尝试一下即可;
坑:n=1的时候输出点1。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
queue<int>q;
int n,m,head[],ct,dis[],t;
double ans;
bool in[];
struct N{
int to,next,w;
N(int t=,int n=,int o=):to(t),next(n),w(o) {}
}edge[];
int main()
{
while(scanf("%d%d",&n,&m)==)
{
t++;
if(!n&&!m)return ;
ct=;
memset(head,,sizeof head);
memset(dis,,sizeof dis);
memset(in,,sizeof in);
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
edge[++ct]=N(y,head[x],z);head[x]=ct;
edge[++ct]=N(x,head[y],z);head[y]=ct;
}
while(q.size())q.pop();
dis[]=;q.push();in[]=;
while(q.size())
{
int x=q.front();q.pop();
in[x]=;
for(int i=head[x];i;i=edge[i].next)
{
int u=edge[i].to;
if(dis[x]+edge[i].w<dis[u])
{
dis[u]=dis[x]+edge[i].w;
if(!in[u])in[u]=,q.push(u);
}
}
}
int k=,dk=;ans=;
for(int i=;i<=n;i++)
if(dis[i]>=ans)//>=以处理n=1的情况
{
ans=dis[i];
k=i;
}
for(int i=head[k];i;i=edge[i].next)
{
int u=edge[i].to;
if(dis[u]+edge[i].w>dis[k]&&ans<1.0*(edge[i].w-dis[k]+dis[u])/+dis[k])
ans=1.0*(edge[i].w-dis[k]+dis[u])/+dis[k],dk=u;
}
printf("System #%d \n",t);
if(dk>k)swap(dk,k);
if(ans==dis[k])
printf("The last domino falls after %.1lf seconds, at key domino %d.\n",ans,k);
else
printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",ans,dk,k);
printf("\n");
}
return ;
}