西安专业网站制作服务/企业推广网站

题目链接Silver Cow Party
思路：
因为路是单向的，所以可以把x当起点，来时的路当边，求出x到各个农场的最短距离，然后将矩阵逆转，将回去时的路当边再求一遍，这样就可以算出从x回到各个农场的最短路。再将两个距离加起来然后循环比较出最大值。

/*Dijkstra算法 单源最短路径，不能处理负值权*/
/*flag = 0表示存储去各个农场去x时的最短路，flag = 1 表示存储x回各个农场时的最短路*/
#include <iostream>
#include <string.h>
#include <cmath>
#define INF 99999999
#define MAXN 1005using namespace std;int vis[MAXN],dis[2][MAXN],map[MAXN][MAXN];/*标记,起点到各个点最短距离，储存图*/int Dijkstra(int start,int flag,int n)/*这里传的n即当做点的个数，也作为循环终点*/
{memset(vis,0,sizeof(vis));for(int i = 1; i <= n; i++){dis[flag][i] = INF;}dis[flag][start] = 0;for(int i = 1; i <= n; i++){int mina = INF;int k;for(int j = 1; j <= n; j++){if(!vis[j]&&dis[flag][j] < mina){mina = dis[flag][j];k = j;}}vis[k] = 1;/*标记结点*/for(int j = 1; j <= n; j++){if(!vis[j]&&dis[flag][j] > dis[flag][k] + map[k][j]){//更新起点到未到达点的最短路，保证disdis[flag][j] = dis[flag][k] + map[k][j]; //中存储的值都是目前位置到点1到该点的最短路径值}}}
}
int main()
{int m,n,x;cin>>n>>m>>x;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j){map[i][j] = 0;}else{map[i][j] = INF;}}}int from,to,s;for(int i = 0; i < m; i++){cin>>from>>to>>s;if(map[from][to] > s){map[from][to] = s;/*防止出现重复边*/}}Dijkstra(x,0,n);for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i > j){swap(map[i][j],map[j][i]);}}}Dijkstra(x,1,n);int ans = 0;for(int i = 1; i <= n; i++){ans = max(ans,dis[0][i] + dis[1][i]);}cout<<ans<<endl;return 0;
}