Silver Cow Party
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 7579 | Accepted: 3354 |
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤
X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road
i requires Ti (1 ≤
Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Line 1: Three space-separated integers, respectively:
N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers:
Ai, Bi, and
Ti. The described road runs from farm
Ai to farm Bi, requiring
Ti time units to traverse.
N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers:
Ai, Bi, and
Ti. The described road runs from farm
Ai to farm Bi, requiring
Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
Sample Input
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
Sample Output
10
http://poj.org/problem?id=3268
这道题是求最短来回路中最长的一条的题目，首先用一个map数组存放每条路径的权，无此路就用0标记，以part farm作为源点，用spfa算法求back路中的最短路径数组，然后倒置矩阵，使得每条路径的方向反转，再用spfa求一次，求得go路的最短路径数组，两个最短路径数组相加，遍历求得最短来回路中最长的一条并输出。
#include <iostream>
#include <queue>
using namespace std;
const int maxf=1001;
const int infi=100000;
int n,m,x;
queue<int> searchg;
void spfa(int *shorttime,char map[][maxf]){
searchg.push(x);
shorttime[x]=0;
int far;
while(!searchg.empty()){
far=searchg.front();
searchg.pop();
for(int i=1;i<=n;++i)
if(map[far][i]!=0&&(shorttime[far]+map[far][i])<shorttime[i]){
shorttime[i]=shorttime[far]+map[far][i];
searchg.push(i);
}
}
}
int main(){
int short1[maxf],short2[maxf],maxt;
char farm1[maxf][maxf];
cin>>n>>m>>x;
memset(farm1,0,sizeof(farm1));
int a,b,t;
for (int i=1;i<=m;++i){
cin>>a>>b>>t;
farm1[a][b]=t;
}
for(int i=1;i<=n;++i){
short1[i]=short2[i]=infi;
}
spfa(short1,farm1);
int temp;
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j){
temp=farm1[i][j];
farm1[i][j]=farm1[j][i];
farm1[j][i]=temp;
}
spfa(short2,farm1);
maxt=0;
for(int i=1;i<=n;++i)
{
short1[i]+=short2[i];
if(short1[i]<2*infi&&short1[i]>maxt)
maxt=short1[i];
}
cout<<maxt<<endl;
return 0;
}