题目描述 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; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017069.html
相关资源：JAVA上百实例源码以及开源项目