这是一道多米诺骨牌的题目 从第一块骨牌出发 问最后一块倒下的骨牌在哪 若是端点 直接输出时间和端点 否则输出时间和 最后的骨牌在哪两块之间

怎么说呢 直接用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;
}
分类: 最短路

发表评论

电子邮件地址不会被公开。 必填项已用*标注