POJ - 3268 Silver Cow Party解题报告（dijkstra分别求单源起点和单源终点的最短路）

题目大意：

题目大意：给你一个有向图，n（1000）个点m（100,000）条路径让你求出各个点到x号点再回到他自己的最短路径的最大值。

分析：

用dijkstra算法可以分别求出各个点到x号点的最短路和x到各个点的最短路。
注意要是用-1来表示该路不通，那代码实现过程中一定要多考虑好多情况。

#include<iostream>
#include<string.h>
#include<math.h>
#define inf 0x3f3f3f3f

using namespace std;

int n,m,x;
int map[1050][1050];
int dis[1050]={0};
int bac[1050]={0};

void my_dijkstra()
{
    int book[1050]={0};
    for(int i=1;i<=n;i++)
    {
        dis[i]=map[i][x];
    }
    for(int i=1;i<n;i++)
    {
        int min=inf;
        int u;
        for(int j=1;j<=n;j++)
        {
            if(book[j]==1)continue;
            if(dis[j]==-1)continue;
            if(dis[j]<min)
            {
                min=dis[j];
                u=j;
            }
        }
        book[u]=1;
        for(int j=1;j<=n;j++)
        {
            if(map[j][u]==-1)continue;
            if(dis[j]>min+map[j][u]||dis[j]==-1)
            {
                dis[j]=min+map[j][u];
            }
        }
    }
}

void my_dijkstra_gai()
{
    int book[1050]={0};
    for(int i=1;i<=n;i++)
    {
        bac[i]=map[x][i];
    }
    for(int i=1;i<n;i++)
    {
        int min=inf;
        int u;
        for(int j=1;j<=n;j++)
        {
            if(book[j]==1)continue;
            if(bac[j]==-1)continue;
            if(bac[j]<min)
            {
                min=bac[j];
                u=j;
            }
        }
        book[u]=1;
        for(int j=1;j<=n;j++)
        {
            if(map[u][j]==-1)continue;
            if(bac[j]>min+map[u][j]||bac[j]==-1)
            {
                bac[j]=min+map[u][j];
            }
        }
    }
}

int main()
{
    while(cin>>n>>m>>x)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                map[i][j]=-1;
                if(i==j)map[i][j]=0;
            }
        }
        for(int i=1;i<=m;i++)
        {
            int ls,le,lv;
            cin>>ls>>le>>lv;
            map[ls][le]=lv;
        }
        my_dijkstra();
        my_dijkstra_gai();
        int max=0;
        for(int i=1;i<=n;i++)
        {
            if(dis[i]==-1||bac[i]==-1)continue;
            if(max<dis[i]+bac[i])
            {
                max=dis[i]+bac[i];
            }
        }
        /*for(int i=1;i<=n;i++)cout<<dis[i]; cout<<endl; for(int i=1;i<=n;i++)cout<<bac[i]; cout<<endl; */
        cout<<max<<endl;
    }
}