这是一道多米诺骨牌的题目 从第一块骨牌出发 问最后一块倒下的骨牌在哪 若是端点 直接输出时间和端点 否则输出时间和 最后的骨牌在哪两块之间
怎么说呢 直接用spfa 算出 从1节点到其他节点的单源最短路径 找出最大的
因为作为最短路的最大值 它必定是一条路径 就算有其他的路径到达这个节点 那也是肯定逼这条最短路径要慢的
所以我们从这个最大节点出发 除了最短路径的其他路径都会是没有走过的路径（也就是还能继续走下去
详见注释
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn=505;
const int inf=0x3f3f3f3f;
int n,m,idx;
int head[maxn],d[maxn];
bool vis[maxn];
struct edge
{
int v,val;
int nxt;
}edges[maxn*maxn];
void init()//初始化
{
memset(head,-1,sizeof head);
memset(vis,false,sizeof vis);
memset(d,0x3f,sizeof d);
idx=0;
}
void add(int u,int v,int val)//邻接表存储
{
edges[idx].v=v;
edges[idx].val=val;
edges[idx].nxt=head[u];
head[u]=idx++;
edges[idx].v=u;
edges[idx].val=val;
edges[idx].nxt=head[v];
head[v]=idx++;
}
void spfa()//spfa算法 都是套路
{
queue<int> que;
que.push(1);
vis[1]=true;
d[1]=0;
while(!que.empty())
{
int tmp=que.front();
que.pop();
vis[tmp]=false;
for(int u=head[tmp];u!=-1;u=edges[u].nxt)
{
int v=edges[u].v;
if(d[tmp]+edges[u].val<d[v])
{
d[v]=d[tmp]+edges[u].val;
if(!vis[v])
{
vis[v]=true;
que.push(v);
}
}
}
}
}
int main()
{
int u,v,cost,test=0;
while(scanf("%d %d",&n,&m),n||m)
{
init();
while(m--)
{
scanf("%d %d %d",&u,&v,&cost);
add(u,v,cost);
}
spfa();
double tim=0.0;//初始化为0.0 避免考虑只有一个多米诺骨牌的情况
int domino=1;
for(int i=2;i<=n;i++)
{
if(tim<d[i])//找到最大的最短路径 并记录
{
tim=(double)d[i];
domino=i;
}
}
int le=domino;
double tt=tim;
bool flag=true;
for(u=head[domino];u!=-1;u=edges[u].nxt)//从该节点出发
{
if(d[u]+edges[u].val!=d[domino])//如果不是最短路径
{
v=edges[u].v;
double tmp=(double)(edges[u].val-(d[domino]-d[v]))/2.0;//计算这条路径上还能走多久
if(tt<tmp+tim)
{
tt=tim+tmp;
le=v;
flag=false;
}
}
}
if(le>domino) swap(le,domino);
printf("System #%d\n",++test);
if(flag) printf("The last domino falls after %.1lf seconds, at key domino %d.\n\n",tim,domino);
else printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n",tt,le,domino);
}
return 0;
}