POJ3268-Silver Cow Party-（Dijstra）

题意：有n只牛聚会，每只牛的家有编号，指定去一只牛家里聚会。牛很懒，走最短路去，花费时间最少。而回来的时间又不相同，问那只走最远的牛走了多久？

解题：去某只牛家里聚会，单源求最短路，来回时间不同，用有向边表示。颠倒一下每条边，则可以得到 去和回 两次最短路，暴力求最大时间。

//记录模板

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s;
int d[1005],d1[1005],d2[1005];
int a[1005][1005];
bool vis[1005];
void Dijkstra()
{
memset(vis,false,sizeof(vis));
memset(d,inf,sizeof(d));
d[s]=0;
while(true)
{
int v=-1;
for(int u=1;u<=n;u++)
{
if( !vis[u] && ( v==-1 || d[u]<d[v] ) )
v=u;
}
if(v==-1)
break;
vis[v]=true;
for(int u=1;u<=n;u++)
d[u]=min(d[u],d[v]+a[v][u]);
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&s)!=EOF)
{
memset(a,inf,sizeof(a));
for(int i=1;i<=n;i++)
a[i][i]=0;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
a[x][y]=min(a[x][y],z);
}
Dijkstra();
for(int i=1;i<=n;i++)///第一次的结果 传给d1
d1[i]=d[i];
///置换矩阵
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)///下三角矩阵转换即可

swap(a[i][j],a[j][i]);
Dijkstra();///从s到各点最短路 即 返回的最短路
int maxx=-inf;
for(int i=1;i<=n;i++)
maxx=max(maxx,d1[i]+d[i]);
printf("%dn",maxx);
}
return 0;
}