POJ 3268 Silver Cow Party （最短路dijkstra）

Silver Cow Party

题目链接：

http://acm.hust.edu.cn/vjudge/contest/122685#problem/D

Description

Input

Output

Sample Input

Sample Output

Hint

##题意：


##题解：


##代码：
``` cpp
#include
#include
#include
#include
#include
#define mid(a,b) ((a+b)>>1)
#define LL long long
#define maxn 1010
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

int n,m;

int value[maxn][maxn];

int dis[maxn];

bool vis[maxn];

int dis2[maxn];

void dijkstra(int s) {

memset(vis, 0, sizeof(vis));

for(int i=1; i<=n; i++) dis[i] = inf;

dis[s] = 0;

for(int i=1; i<=n; i++) {

    int p, mindis = inf;

    for(int j=1; j<=n; j++) {

        if(!vis[j] && dis[j]<mindis)

            mindis = dis[p=j];

    }

    vis[p] = 1;

    for(int j=1; j<=n; j++) {

        if(dis[j] > dis[p]+value[p][j]) {

            dis[j] = dis[p] + value[p][j];

        }

    }

}

}

void dijkstra2(int s) {

memset(vis, 0, sizeof(vis));

for(int i=1; i<=n; i++) dis2[i] = inf;

dis2[s] = 0;

for(int i=1; i<=n; i++) {

    int p, mindis = inf;

    for(int j=1; j<=n; j++) {

        if(!vis[j] && dis2[j]<mindis)

            mindis = dis2[p=j];

    }

    vis[p] = 1;

    for(int j=1; j<=n; j++) {

        if(dis2[j] > dis2[p]+value[j][p]) {

            dis2[j] = dis2[p] + value[j][p];

        }

    }

}

}

int main(int argc, char const *argv[])

{

//IN;

int aim;

while(scanf("%d %d %d", &n,&m,&aim) != EOF)

{

    for(int i=1; i<=n; i++)

        for(int j=1; j<=n; j++)

            value[i][j] = inf;

    while(m--){

        int u,v,w; cin>>u>>v>>w;

        if(w < value[u][v]) value[u][v] = w;

    }

    dijkstra(aim);

    dijkstra2(aim);

    int ans = 0;

    for(int i=1; i<=n; i++) if(dis[i]!=inf && dis2[i]!=inf)

        ans = max(ans, dis[i]+dis2[i]);

    printf("%d\n", ans);

}

return 0;

}