来回最短路POJ3268

时间:2021-11-16 03:48:22

这个题得主要考点在于给你的图是去了再回来得有向图,如何模块化解决呢就是转变图的方向,我们根据初始得放心求出每个点到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\n",ans);
}
return 0;
}