D - Silver Cow Party (逆置矩阵，Dijkstra,bellman_ford,floyd）

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;
}