题目描述 Description
小S 想要从某地出发去同学k的家中参加一个party，但要有去有回。他想让所用的时间尽量的短。但他又想知道从不同的点出发，来回的最短时间中最长的时间是多少，这个任务就交给了你输入描述 Input Description
第一行三个正整数n, m, k(n是节点个数，m是有向边的条数，k是参加聚会的地点编号(1 ≤ n ≤ 1000 ,1 ≤ m ≤ 100,000)
第二行..m + 1行每行3个整数x，y，w 代表从x到y需要花w的时间 0 < w <= 100输出描述 Output Description
输出从不同的节点出发的最短时间中最长的时间样例输入 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
注意是有向图哦，千万记得跑不到的情况！就只因为这个，我最后一个点WA很多遍……
另外，这是一个n2logn的做法…… 后来@Loi_a大神一说，我才想起来有nlogn的做法。Orrrrrrrrrrrrrz
nlogn的做法请戳 Loi_a
Loi_a : 这题数据水到不行…… (Orz)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 100010;
struct Edge
{int from, to, cost;
}es[MAXN];
int first[MAXN], nxt[MAXN], tot = 1;
long long d[MAXN], dis[MAXN], maxx;
bool used[MAXN];
int n, m, k;
queue < int > q;void build(int f, int t, int d)
{es[++tot].cost = d;es[tot].from = f;es[tot].to = t;nxt[tot] = first[f];first[f] = tot;
}void csh()
{memset(used, 0, sizeof(used));for(int i = 1; i <= n; i++){dis[i] = 2147483;}
}void spfa(int s)
{d[s] = 0;q.push(s);used[s] = 1;while(!q.empty()){int u = q.front();q.pop();used[u] = 0;for(int i = first[u]; i != -1; i = nxt[i]){int v = es[i].to;if(d[v] > d[u] + es[i].cost){d[v] = d[u] + es[i].cost;if(!used[v]){q.push(v);used[v] = 1;}} }}
}void spfa_1(int s)
{dis[s] = 0;q.push(s);used[s] = 1;while(!q.empty()){int u = q.front();q.pop();used[u] = 0;for(int i = first[u]; i != -1; i = nxt[i]){int v = es[i].to;if(dis[v] > dis[u] + es[i].cost){dis[v] = dis[u] + es[i].cost;if(!used[v]){q.push(v);used[v] = 1;}} }}
}int main()
{scanf("%d%d%d", &n, &m, &k);memset(first, -1, sizeof(first));for(int i = 1; i <= n; i++){d[i] = 2147483;}int x, y, w;for(int i = 1; i <= m; i++){scanf("%d%d%d", &x, &y, &w);build(x, y, w);}spfa(k);for(int i = 1; i <= n; i++){if(i == k)continue;csh();spfa_1(i);if(dis[k] != 2147483 && d[i] != 2147483) //判断是否能跑到 maxx = max(dis[k] + d[i], maxx);}cout<<maxx;return 0;
}
