Silver Cow Party(最短路）

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

---

题意

n个农场，每个农场的奶牛都去x农场聚会，然后再回去。奶牛喜欢走最短的路程，农场之单向联通。走每条路都要花费时间，问花费时间最多的奶牛耗时多少。给出m条边，和走每条边花费的时间

思路

1.先计算从X到所有点的最短路

2.将所给边反向录入，得到从各点到x最短路

3.两次最短路相加，找花费最大的那一条

---

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1210
int e[N][N],dis[N];
int dis2[N],book[N];
int n,m,x;
void dijstra(int x,int dis[]) {

    int u,minn;
    memset(book,0,sizeof(book));
    book[x]=1;
    for(int i=1; i<=n; i++)
        dis[i]=e[x][i];

    for(int i=1; i<n; i++) {
        minn=inf;
        for(int j=1; j<=n; j++)    //板子千万别打错
            if(minn>dis[j]&&!book[j]) {
                minn=dis[j];
                u=j;
            }
            book[u]=1;
            for(int v=1; v<=n; v++)
                if(dis[v]>e[u][v]+dis[u])
                    dis[v]=e[u][v]+dis[u];
    }
}
int main() {
    int t1,t2,t3;
    while(~scanf("%d%d%d",&n,&m,&x)) {
         for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++) {
                if(i==j) e[i][j]=0;
                else e[i][j]=inf;
            }
        while(m--) {
            scanf("%d%d%d",&t1,&t2,&t3);
            e[t1][t2]=min(e[t1][t2],t3);
        }
        dijstra(x,dis);
        for(int i=1; i<=n; i++)
            for(int j=i+1; j<=n; j++)
                swap(e[i][j],e[j][i]);
        dijstra(x,dis2);
        int mx=-1;
        for(int i=1; i<=n; i++)
            mx=max(mx,dis[i]+dis2[i]);
        printf("%d\n",mx);
    }
    return 0;
}