POJ 3268 Silver Cow Party (单源最短路Dijkstra+反向构图)

题目链接

POJ3268

题目大意

给定一个有N(1 ≤ N ≤ 1000)个结点、M(1 ≤ M ≤ 105 )条单向边的有向正权图，求每个结点出发到X号结点再回来到初始位置的花费的最小值。

分析

对于每个结点，要在它与X号结点之间走一个来回花费最小，必定它到X要走最短路，从X回到它也要走最短路。
返回的最短路好解决，即X号结点出发到其他结点的单源最短路，用Dijkstra算法跑一遍即可。现在关键要解决从其他结点到X号结点的最短路，这种情况下起点是多个，而终点是一个，与单源最短路径的情况恰好相反，如果再每个点作为起点用Dijkstra复杂度就较高了。处理方法是：反向建图，再求X到其他结点的单源最短路。(道路反向，起点与终点互换，问题等效)
最后答案为Max(dis[i],dis2[i]).

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define Max(a,b) (a>b?a:b)
using namespace std;
const int INF=99999999;
const int MAXN=1010;
const int MAXM=100010;
int e[MAXN][MAXN],e2[MAXN][MAXN],dis[MAXN],dis2[MAXN],book[MAXN],book2[MAXN];
int n,m,x;
void Init()//邻接矩阵初始化
{
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
e[i][j]=(i==j?0:INF);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
e2[i][j]=(i==j?0:INF);
}
void Dijkstra()
{
int i,j,u,v,mind;
for (i=1;i<=n;i++)
dis[i]=e[x][i];
memset(book,0,sizeof(book));
book[x]=1;
for (i=1;i<=n-1;i++)
{
mind=INF;
for (j=1;j<=n;j++)
if (dis[j]<mind&&!book[j])
{
mind=dis[j];
u=j;
}
book[u]=1;
for (v=1;v<=n;v++)
if ((e[u][v]<INF)&&(dis[v]>dis[u]+e[u][v]))
dis[v]=dis[u]+e[u][v];
}
}
void Dijkstra2()//对反向图的计算
{
int i,j,u,v,mind;
for (i=1;i<=n;i++)
dis2[i]=e2[x][i];
memset(book2,0,sizeof(book2));
book2[x]=1;
for (i=1;i<=n-1;i++)
{
mind=INF;
for (j=1;j<=n;j++)
if (dis2[j]<mind&&!book2[j])
{
mind=dis2[j];
u=j;
}
book2[u]=1;
for (v=1;v<=n;v++)
if ((e2[u][v]<INF)&&(dis2[v]>dis2[u]+e2[u][v]))
dis2[v]=dis2[u]+e2[u][v];
}
}
int main()
{
int a,b,c,i,ans;
scanf("%d%d%d",&n,&m,&x);
Init();
while (m--)
{
scanf("%d%d%d",&a,&b,&c);
e[a][b]=c;
e2[b][a]=c;//反向建图
}
Dijkstra();
Dijkstra2();
ans=-1;
for (i=1;i<=n;i++)
ans=Max(ans,dis[i]+dis2[i]);
printf("%dn",ans);
return 0;
}

最后

以上就是伶俐海燕为你收集整理的POJ 3268 Silver Cow Party (单源最短路Dijkstra+反向构图)的全部内容，希望文章能够帮你解决POJ 3268 Silver Cow Party (单源最短路Dijkstra+反向构图)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。