Silver Cow Party POJ - 3268（最短路 Dijkstra）

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 Ti (1 ≤ Ti ≤ 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: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output

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

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

10

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.

**

题意：

求i号农场牛到x农场参加活动并回到自己的农场所需花费的最小时间
输出所有牛中花费时间最多的牛所花费的时间。

思路：

先计算每个牛去参加活动所需花费的最小时间，在计算每个牛从x农场回到自己农场花费的最小时间，两个加起来，在比较哪头牛花费的时间最多，并且输出。 最短路模板可以实现
这个题用Dijkstra算法来写！

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int e[1010][1010],book[1010],dis1[1010],dis2[1010];
int inf=99999999;
int main()
{
    int n,m,x;
    while(~scanf("%d %d %d",&n,&m,&x))
    {
        int a,b,t,i,j,u,v;
        for(i=1;i<=n;i++)   //初始化
        {
            for(j=1;j<=n;j++)
            {
                if(i==j)
                    e[i][j]=0;
                else
                    e[i][j]=inf;
            }
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&b,&t);
            e[a][b]=t;
        }

        for(i=1;i<=n;i++)
        {
            dis1[i]=e[i][x];
            dis2[i]=e[x][i];
        }
        memset(book,0,sizeof(book));
        int min1,min2;
        /*最短路Dijkstra模板*/
        for(i=1;i<n;i++)//计算从i农场到 x农场的最小花费时间
        {
            min1=inf;
            for(j=1;j<=n;j++)
            {
                if(!book[j]&&dis1[j]<min1)
                {
                    min1=dis1[j];
                    u=j;
                }
            }
            book[u]=1;
            for(v=1;v<=n;v++)
            {
                if(book[v]==0&&dis1[v]>dis1[u]+e[v][u]) //e[u][v]中注意v在前u在后表示去X农场参加活动
                    dis1[v]=dis1[u]+e[v][u];
            }
        }
        memset(book,0,sizeof(book));
        for(i=1;i<n;i++) //计算从X农场到i农场的最小花费时间
        {
            min2=inf;
            for(j=1;j<=n;j++)
            {
                if(!book[j]&&dis2[j]<min2)
                {
                    min2=dis2[j];
                    u=j;
                }
            }
            book[u]=1;
            for(v=1;v<=n;v++)
            {
                if(book[v]==0&&dis2[v]>dis2[u]+e[u][v]) //u在前v在后相当于反转路 这里一定要注意，否则会一直WA的
                    dis2[v]=dis2[u]+e[u][v];
            }
        }
        int maxx=-9999;
        for(i=1;i<=n;i++)  //最后比较输出
        {
           maxx=max(maxx,dis1[i]+dis2[i]);
        }
        printf("%d\n",maxx);
    }
    return 0;
}