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.
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
/*經典題型，先求一次所有點到x的最短距離，
存在dis1數組中，之後把矩陣轉置一下
再求從x出發回到家的最短距離，存在dis2數組中
最後把dis1數組和dis2數組合并到dis數組
再求dis數組中的最大值就行了。
這裡求最短距離的方法可以用Dijkstra，Bellma_ford或者spfa;
*/
//這裡是DIjkstra的做法
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int map[1005][1005];
int dis1[1005],dis2[1005];
int visited[1005];
int n,m,x;
void Dijsktra1(int x)
{
memset(visited,0,sizeof(visited));
visited[x]=1;
for(int i = 1;i<=n;i++)
dis1[i]=map[x][i];
dis1[x]=0;
for(int i = 1;i<=n-1;i++){
int minn=INF,k;
for(int j = 1;j<=n;j++)
if(minn>dis1[j]&&!visited[j])
minn=dis1[k=j];
visited[k]=1;
for(int j = 1;j<=n;j++)
if(dis1[j]>(dis1[k]+map[k][j])&&!visited[j])
dis1[j]=dis1[k]+map[k][j];
}
}
void Dijsktra2(int x)
{
memset(visited,0,sizeof(visited));
visited[x]=1;
for(int i = 1;i<=n;i++)
dis2[i]=map[x][i];
dis2[x]=0;
for(int i = 1;i<=n-1;i++){
int minn=INF,k;
for(int j = 1;j<=n;j++)
if(minn>dis2[j]&&!visited[j])
minn=dis2[k=j];
visited[k]=1;
for(int j = 1;j<=n;j++)
if(dis2[j]>(dis2[k]+map[k][j])&&!visited[j])
dis2[j]=dis2[k]+map[k][j];
}
}
int main(int argc, char** argv) {
while(scanf("%d %d %d",&n,&m,&x)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
map[i][j]=(i==j)?0:INF;
for(int i = 1;i<=m;i++){
int a,b,cost;
scanf("%d %d %d",&a,&b,&cost);
if(map[a][b]>cost)//可能會有重複的路徑，用Dijkstra的時候要注意
map[a][b]=cost;
}
Dijsktra1(x);//求一次到x最短距離
for(int i = 1;i<=n;i++){
for(int j = i+1;j<=n;j++){
int temp;
temp=map[j][i];
map[j][i]=map[i][j];
map[i][j]=temp;
}
}//矩陣轉置，也可以用指針
Dijsktra2(x); //再求回去的最短距離
int dis[1005]={0};
for(int i = 1;i<=n;i++)
dis[i]=dis1[i]+dis2[i];//合并求最大值
printf("%d\n",*max_element(dis+1,dis+n+1));
}
return 0;
}
//bellman_ford算法
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define INF 0x3f3f3f
using namespace std;
int dis1[1005],dis2[1005];
int n,m,x;
struct Edge{
int from,to,cost;
}edge[100005];
void bellman_ford1(int s)
{
for(int i = 1;i<=n;i++)
dis1[i]=INF;
dis1[s]=0;
for(int i = 1;i<=n-1;i++){
for(int j = 1;j<=m;j++){
int s=edge[j].from;
int e=edge[j].to;
int c=edge[j].cost;
if(dis1[e]>dis1[s]+c)
dis1[e]=dis1[s]+c;
}
}
}
void bellman_ford2(int s)
{
for(int i = 1;i<=n;i++)
dis2[i]=INF;
dis2[s]=0;
for(int i = 1;i<=n-1;i++){
for(int j = 1;j<=m;j++){
int s=edge[j].from;
int e=edge[j].to;
int c=edge[j].cost;
if(dis2[e]>dis2[s]+c)
dis2[e]=dis2[s]+c;
}
}
}
int main(int argc, char** argv) {
scanf("%d%d%d",&n,&m,&x);
for(int i = 1;i<=m;i++){
int a,b,cost;
scanf("%d%d%d",&a,&b,&cost);
edge[i].from=a;
edge[i].to=b;
edge[i].cost=cost;
}
bellman_ford1(x);
for(int i = 1;i<=m;i++)
swap(edge[i].from,edge[i].to);//起點和終點換一下
bellman_ford2(x);
int dis[1010]={0};
for(int i =1;i<=n;i++)
dis[i]=dis1[i]+dis2[i];
printf("%d\n",*max_element(dis+1,dis+1+n));
return 0;
}
//spfa算法-鄰接矩陣
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<queue>
#define INF 0x3f3f3f
using namespace std;
int dis1[1005],dis2[1005];
int visited[1005];
int n,m,x;
int G1[1005][1005];
int G2[1005][1004];
void spfa1(int s)
{
queue<int> q;
memset(visited,0,sizeof(visited));
for(int i = 1;i<=n;i++)
dis1[i]=INF;
dis1[s]=0;
q.push(s);
visited[s]=1;
while(!q.empty())
{
int k=q.front();
q.pop();
visited[k]=0;
for(int i = 1;i<=n;i++){
if(dis1[i]>dis1[k]+G1[k][i]){
dis1[i]=dis1[k]+G1[k][i];
if(!visited[i]){
q.push(i);
visited[i]=1;
}
}
}
}
}
void spfa2(int s)
{
queue<int> q;
memset(visited,0,sizeof(visited));
for(int i = 1;i<=n;i++)
dis2[i]=INF;
dis2[s]=0;
q.push(s);
visited[s]=1;
while(!q.empty())
{
int k=q.front();
q.pop();
visited[k]=0;
for(int i = 1;i<=n;i++){
if(dis2[i]>dis2[k]+G2[k][i]){
dis2[i]=dis2[k]+G2[k][i];
if(!visited[i]){
q.push(i);
visited[i]=1;
}
}
}
}
}
int main(int argc, char** argv) {
scanf("%d%d%d",&n,&m,&x);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
G1[i][j]=(i==j)?0:INF;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
G2[i][j]=(i==j)?0:INF;
for(int i = 1;i<=m;i++){
int a,b,cost;
scanf("%d%d%d",&a,&b,&cost);
G1[a][b]=cost;
G2[b][a]=cost;
}
spfa1(x);
spfa2(x);
int dis[1010]={0};
for(int i =1;i<=n;i++)
dis[i]=dis1[i]+dis2[i];
printf("%d\n",*max_element(dis+1,dis+1+n));
return 0;
}
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)