图论 ---- spfa + 链式向前星 ---- poj 3268 : Silver Cow Party-阿里云开发者社区

图论 ---- spfa + 链式向前星 ---- poj 3268 : Silver Cow Party

2014-08-07 1035

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Silver Cow Party Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 12674 Accepted: 5651 Description One cow from ...

Silver Cow Party

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 12674		Accepted: 5651

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires T_i (1 ≤ T_i ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2.. M+1: Line i+1 describes road i with three space-separated integers: A_i, B_i, and T_i. The described road runs from farm A_i to farm B_i, requiring T_i time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

Sample Output

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

Source

USACO 2007 February Silver

Mean:

原意：草场上有n个农场，农场之间有一些路径，每个农场里住着一头牛，现在x农场的牛要过生日开party，其他农场的牛要到该农场去参加party，现在让你选择一头来回耗时最多的一头牛出来，输出时间。

给你一个n个结点、m条边的有向图，现在要你求从n-1个结点到达指定的一个结点的来回最长路。

analyse:

这题思路很巧妙，我们在存图的时候用链式向前星来存，存的时候就建两次边，一次正向，一次反向，用一个flag来标记一下。然后用两遍spfa，第一遍求出从x点出发的正向图到每个结点的最短路，第二遍求出从x点出发的反向图到每个结点的最短路，最后将两次的最短路对应相加，求出最大值即为最终的answer。

Time complexity：O(n*k)

Source code：

//Memory   Time
// 3521K    241MS
//by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAXV 1010
#define MAXE 100010
#define LL long long
using namespace std;
namespace Adj
{
    struct Node
    {
        int to,next,val;
        bool flag;
    } edge[MAXE<<1];
    int top,head[MAXV];
    void init()
    {
        top=1;
        memset(head,0,sizeof(head));
    }
    void addEdge(int u,int v,int val)
    {
        edge[top].to=v;
        edge[top].val=val;
        edge[top].flag=1;
        edge[top].next=head[u];
        head[u]=top++;

        edge[top].to=u;
        edge[top].val=val;
        edge[top].flag=0;
        edge[top].next=head[v];
        head[v]=top++;
    }
}
using namespace Adj;
int n,m,x,ans;
bool vis[MAXV];
int dis[MAXV];
int dis1[MAXV];
void spfa(bool flag)
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;i++)
        dis[i]=INT_MAX;
    queue<int>Q;
    Q.push(x);
    vis[x]=1;
    dis[x]=0;
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=edge[i].next)
        {
            if(flag==1)
            {
                if(edge[i].flag==0)
                    continue;
            }
            else
            {
                if(edge[i].flag==1)
                    continue;
            }
            int son=edge[i].to;
            int val=edge[i].val;
            if(dis[now]+val<dis[son])
            {
                dis[son]=dis[now]+val;
                if(!vis[son])
                {
                    vis[son]=1;
                    Q.push(son);
                }
            }
        }
    }
    if(flag==1)
    {
        for(int i=1;i<=n;i++)
            dis1[i]=dis[i];
    }
    else
    {
        int Max=INT_MIN;
        for(int i=1;i<=n;i++)
        {
            dis[i]+=dis1[i];
            if(dis[i]>Max)
                Max=dis[i];
        }
        ans=Max;
    }
}

int main()
{
//    freopen("cin.txt","r",stdin);
//    freopen("cout.txt","w",stdout);
    while(~scanf("%d %d %d",&n,&m,&x))
    {
        init();
        int u,v,w;
        while(m--)
        {
            scanf("%d %d %d",&u,&v,&w);
            addEdge(u,v,w);
        }
        spfa(1);
        spfa(0);
        printf("%d\n",ans);
    }
    return 0;
}