最短路径问题 POJ 3268

解题思路：最短路径只需要从x到i的最短路径代表他们返回的最短路径，然后将所有边反过来，再从x到i的最短路径代表他们来参加聚会的最短路径，这样对应相加找出一个最大值就可以了，当然其实不需要将所有边反过来，在dijkstra里面两次查询i到x最短路dis[i],和从x回到i的最短返回距离disf[i].然后找出和的最大值即可

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define N 1100
int n,m,x;
int dis[N],disf[N],maps[N][N],vis[N];

void init(int n)
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
           maps[i][j]=(i==j)?0:INF;
}

int dijkstra()
{
    int i,j,index,Min;
    for(i=1;i<=n;i++)
    {
        dis[i]=maps[i][x]; ///i到x的最短路~
        disf[i]=maps[x][i]; ///x返回i的最短路~
        vis[i]=0;
    }

    for(i=1;i<=n;i++)
    {
        Min=INF;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && Min>dis[j])
            {
                Min=dis[j];
                index=j;
            }
        }
        vis[index]=1;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && dis[j]>Min+maps[j][index])
                dis[j]=Min+maps[j][index];
        }
    }

    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;i++)
    {
        Min=INF;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && Min>disf[j])
            {
                Min=disf[j];
                index=j;
            }
        }
        vis[index]=1;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && disf[j]>Min+maps[index][j])
                disf[j]=Min+maps[index][j];
        }
    }

    int Max=-1;
    for(i=1;i<=n;i++)
    {
        if(Max<dis[i]+disf[i])
            Max=dis[i]+disf[i];
    }
    return Max;
}

int main()
{
    int i,a,b,c,ans;
    while(scanf("%d%d%d",&n,&m,&x)!=EOF)
    {
        init(n);
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            maps[a][b]=c;
        }
        ans=dijkstra();
        printf("%d\n",ans);
    }
    return 0;
}

最短路径问题 POJ 3268

相关推荐