poj 3268 Silver Cow Party(最短路,正反两次,这个模版好)

时间:2020-12-12 20:03:01

题目

Dijkstra,正反两次最短路,求两次和最大的。

#define  _CRT_SECURE_NO_WARNINGS
//这是找出最短路加最短路中最长的来回程
//也就是正反两次最短路相加找最大的和
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int MAXN=; #define typec int
const typec INF=0x3f3f3f3f;//防止后面溢出,这个不能太大
bool vis[MAXN];
typec cost1[MAXN][MAXN],cost2[MAXN][MAXN];
typec lowcost1[MAXN],lowcost2[MAXN];
void Dijkstra1(int n,int beg)
{
for(int i=;i<=n;i++)
{
lowcost1[i]=cost1[beg][i];vis[i]=false;
}
for(int i=;i<=n;i++)
{
typec temp=INF;
int k=-;
for(int j=;j<=n;j++)
{
if(!vis[j]&&lowcost1[j]<temp)
{
temp=lowcost1[j];
k=j;
}
}
vis[k]=true;
for(int l=;l<=n;l++)
{
if(!vis[l])
{
lowcost1[l]=min(lowcost1[l],lowcost1[k]+cost1[k][l]);
}
}
}
}
void Dijkstra2(int n,int beg)
{
for(int i=;i<=n;i++)
{
lowcost2[i]=cost2[beg][i];vis[i]=false;
}
for(int i=;i<=n;i++)
{
typec temp=INF;
int k=-;
for(int j=;j<=n;j++)
{
if(!vis[j]&&lowcost2[j]<temp)
{
temp=lowcost2[j];
k=j;
}
}
vis[k]=true;
for(int l=;l<=n;l++)
{
if(!vis[l])
{
lowcost2[l]=min(lowcost2[l],lowcost2[k]+cost2[k][l]);
}
}
}
} int main()
{
int n,m,t,i,j,a,b,c;
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
for(i=;i<=n;i++)
for(j=;j<=n;j++)
cost1[i][j]=cost2[i][j]=(i==j)? :INF; for(i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(cost1[a][b]>c)
{
cost1[a][b]=c;//正
}
if(cost2[b][a]>c)
{
cost2[b][a]=c;//反
}
}
Dijkstra1(n,t);//正
Dijkstra2(n,t);//反
int ans=-;
for(i=;i<=n;i++)
{
lowcost1[i]+=lowcost2[i];
ans=ans>lowcost1[i]? ans:lowcost1[i];
}
printf("%d\n",ans);
} return ;
}