来回最短路POJ3268

这个题得主要考点在于给你的图是去了再回来得有向图，如何模块化解决呢就是转变图的方向，我们根据初始得放心求出每个点到x得最短路，然后转变所有路得方向再求出所有点到x得最短路，最后一相加就是最后的来回了~~
实现得时候我用到了数组指针，感觉非常得方便

#include <iostream>
#include <string.h>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1010;
int mp[maxn][maxn];
int remp[maxn][maxn];
int dis[maxn];
int redis[maxn];
int vis[maxn];
int n,m,x;
void init(int n)
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(i == j)
            {
                mp[i][j] = 0;
                remp[i][j] = 0;
            }
            else
            {
                mp[i][j] = inf;
                remp[i][j] = inf;
            }
        }
    }
}
void Dijkstra(int s,int (*p)[1010],int *d)
{
    for(int i = 1;i <= n;i++)
    {
        d[i] = p[s][i];
        vis[i] = 0;
    }
    vis[s] = 1;
    for(int i = 1;i <= n;i++)
    {
        int minlen = inf,net = 0;
        for(int j = 1;j <= n;j++)
        {
            if(!vis[j] && d[j] < minlen)
            {
                minlen = d[j];
                net = j;
            }
        }
        if(net == 0)break;
        vis[net] = 1;
        for(int j = 1;j <= n;j++)
        {
            if(!vis[j])
            {
                d[j] = min(d[j],d[net] + p[net][j]);
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&x))
    {
        init(n);
        int a,b,l;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&l);
            if(mp[a][b] > l)
            {
                mp[a][b] = l;
                remp[b][a] = l;
            }
        }
        Dijkstra(x,mp,dis);
        Dijkstra(x,remp,redis);
        int ans = 0;
        for(int i = 1;i <= n;i++)
        {
            ans = max(ans,dis[i] + redis[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}