POJ3268-Silver Cow Party-（Dijstra）

题意：有n只牛聚会，每只牛的家有编号，指定去一只牛家里聚会。牛很懒，走最短路去，花费时间最少。而回来的时间又不相同，问那只走最远的牛走了多久？

解题：去某只牛家里聚会，单源求最短路，来回时间不同，用有向边表示。颠倒一下每条边，则可以得到去和回两次最短路，暴力求最大时间。

//记录模板

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

int n,m,s;
int d[1005],d1[1005],d2[1005];
int a[1005][1005];
bool vis[1005];

void Dijkstra()
{
    memset(vis,false,sizeof(vis));
    memset(d,inf,sizeof(d));
    d[s]=0;
    while(true)
    {
        int v=-1;
        for(int u=1;u<=n;u++)
        {
            if( !vis[u] && ( v==-1 || d[u]<d[v] ) )
                v=u;
        }
        
        if(v==-1)
            break;
        vis[v]=true;
        
        for(int u=1;u<=n;u++)
            d[u]=min(d[u],d[v]+a[v][u]);
    }
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    {
        memset(a,inf,sizeof(a));
        for(int i=1;i<=n;i++)
        a[i][i]=0;

        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            a[x][y]=min(a[x][y],z);
        }

        Dijkstra();

        for(int i=1;i<=n;i++)///第一次的结果 传给d1
            d1[i]=d[i];

        ///置换矩阵
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)///下三角矩阵转换即可
            swap(a[i][j],a[j][i]);

        Dijkstra();///从s到各点最短路 即 返回的最短路
        
        int maxx=-inf;
        for(int i=1;i<=n;i++)
            maxx=max(maxx,d1[i]+d[i]);
        printf("%d
",maxx);
    }
    return 0;
}

Dijkstra模板

POJ3268-Silver Cow Party-（Dijstra）

相关推荐