最短路 Silver Cow Party
程序员文章站
2022-07-13 11:29:37
...
有向图,求往返路径,方法是正向和反向存两次邻接矩阵,用两次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;
}