题解 P1821 【[USACO07FEB]银牛派对Silver Cow Party】

· · 题解

【[USACO07FEB]银牛派对Silver Cow Party】

Tips:博客内食用效果更佳 传送门

题意：

有n头牛，m条路，所有牛要前往X牛的家开趴（当然X牛不用动），求其他牛去开趴来回的最短距离，输出最长的那条。

简化版题意：

有n个节点，m条边，给出终点X，求其他节点到终点的来回最短距离，输出最长的距离。

注意：该题所给的边为有向边，别瞎*2输出

使用的算法：SPFA

思路：

题目要找其他点到终点X的最短路径和终点X到其他点的最短路径。为便于代码实现，要进行反向建图，用SPFA跑正向的图求终点X到其他点的最短路径，再用跑反向图求其他点到终点X的最短路径。

反向图即将边的起点和终点反过来，边权不变。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
struct edge
{
    int u,v;    
};

vector<edge> G[3][1001];//动态数组存边

queue<int> Q;//队列（STL大法好）

int n,m,f[3][1001],l,ans;
bool vis[1001];

void spfa(int k)//k=1时正向图，k=2时反向图
{
    memset(vis,0,sizeof(vis));//初始化false
    vis[l]=true;
    f[k][l]=0;
    Q.push(l);
    while(!Q.empty())
    {
        int news=Q.front();
        Q.pop();
        vis[news]=false;
        for(int i=0;i<G[k][news].size();i++)
        {
            int v=G[k][news][i].v,u=G[k][news][i].u;
            if(f[k][v]>f[k][news]+u)
            {
                f[k][v]=f[k][news]+u;
                if(!vis[v])
                {
                    vis[v]=true;
                    Q.push(v);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&l);
    memset(f,0x3f3f3f,sizeof(f));
    for(int a=1;a<=m;a++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge cmp;
        cmp.v=y;
        cmp.u=z;
        G[1][x].push_back(cmp);//正向建图
        cmp.v=x;
        G[2][y].push_back(cmp);//反向建图
    }
    spfa(1);//跑正向图
    spfa(2);//跑反向图
    for(int a=1;a<=n;a++)
    {
        if(a==l)
        {
            continue;
        }
        ans=max(f[1][a]+f[2][a],ans);//找最长的
    }
    printf("%d\n",ans);
    return 0;
}