欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路 Silver Cow Party

程序员文章站 2022-07-13 11:29:37
...

最短路 Silver Cow Party

有向图,求往返路径,方法是正向和反向存两次邻接矩阵,用两次dij

#include <iostream>
#include <memory.h>
#define IN (1<<28)
using namespace std;

int G1[1005][1005],G2[1005][1005];
int N,M,X;
int dist1[1005];
int visited[1005];
int dist2[1005];
void dij1()
{
    for( int i = 1; i <= N; i++ )
        dist1[i] = G1[X][i];
    memset(visited, 0, sizeof(visited));
    dist1[X] = 0;
    visited[X] = 1;
    while(1)
    {
        int MinV = 0;
        int Min = IN;
        for( int i = 1; i <= N; i++ )
        {
            if( !visited[i] && dist1[i] < Min )
            {
                MinV = i;
                Min = dist1[i];
            }
        }
        if( !MinV )
            break;
        visited[MinV] = 1;
        for( int i = 1; i <= N; i++ )
        {
            if( !visited[i] && dist1[i] > dist1[MinV] + G1[MinV][i] )
            {
                dist1[i] = dist1[MinV] + G1[MinV][i];
            }
        }
    }
    return;
}
void dij2()
{
    for( int i = 1; i <= N; i++ )
        dist2[i] = G2[X][i];
    memset(visited, 0, sizeof(visited));
    dist2[X] = 0;
    visited[X] = 1;
    while(1)
    {
        int MinV = 0;
        int Min = IN;
        for( int i = 1; i <= N; i++ )
        {
            if( !visited[i] && dist2[i] < Min )
            {
                MinV = i;
                Min = dist2[i];
            }
        }
        if( !MinV )
            break;
        visited[MinV] = 1;
        for( int i = 1; i <= N; i++ )
        {
            if( !visited[i] && dist2[i] > dist2[MinV] + G2[MinV][i] )
            {
                dist2[i] = dist2[MinV] + G2[MinV][i];
            }
        }
    }
    return;
}
int main()
{
    cin >> N >> M >> X;
    for( int i = 1; i <= N; i++ )
        for( int j = 1; j <= N; j++ )
        {
            if( i==j )
            {
                G1[i][j] = 0;
                G2[i][j] = 0;
            }
            else
            {
                G1[i][j] = IN;
                G2[i][j] = IN;
            }
        }
    while( M-- )
    {
        int Begin,End,Length;
        cin >> Begin >> End >> Length;
        G1[Begin][End] = Length;
        G2[End][Begin] = Length;
    }
    int Max = 0;
    dij1();
    dij2();
    for( int i = 1; i <= N; i++ )
    {
        Max = max(Max, dist1[i] + dist2[i]);
    }
    cout << Max << endl;
    return 0;
}