原题链接
题目描述：最近，Elaxia和w的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能的长。现在已知的是Elaxia和w所在的宿舍和实验室的编号以及学校的地图：地图上有N个路口，M条路，经过每条路都需要一定的时间。具体地说，就是要求无向图中，两对点间最短路的最长公共路径。
输入格式：第一行：两个整数N和M（含义如题目描述）。 第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别x1,y1和x2,y2）。 接下来M行：每行三个整数，u、v、l（1≤u≤N，1≤v≤N，1≤l≤10000），表u和v之间有一条路，经过这条路所需要的时间为l。
输出格式：一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。
输入样例： 9 10 1 6 7 8 1 2 1 2 5 2 2 3 3 3 4 2 3 9 5 4 5 3 4 6 4 4 7 2 5 8 1 7 9 1
输出样例： 3
解析：好恶心的一题啊，居然卡内存。 看到题目就想到要建最短路图，可之后就不知道怎么做了。 看到dalao们的题解后才知道要建成单向边后做DAG上的DP。 之后好像没什么难点了。
代码如下：
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> using namespace std; const int maxn = 1505; int n, m, x1, y1, x2, y2, ans, dp[maxn]; int dis1[maxn], dis2[maxn], dis3[maxn], dis4[maxn], vis[maxn]; int w[maxn][maxn], x[600001], y[600001], val[600001], du[maxn]; int nxt[600001], to[600001], vall[600001], cnt, hed[600001]; //只有开600000才能过。。。 struct node{ int dis, ind; bool operator <(const node &a)const{ return a.dis < dis; } }; priority_queue <node> heap; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void add(int x, int y, int v) { nxt[++ cnt] = hed[x]; hed[x] = cnt; to[cnt] = y; vall[cnt] = v; } void dijkstra(int s, int *dis) { for (int i = 1; i <= n; ++ i) dis[i] = 2e9, vis[i] = 0; dis[s] = 0; heap.push((node){0, s}); while (!heap.empty()) { node u = heap.top(); heap.pop(); if (vis[u.ind]) continue; vis[u.ind] = 1; for (int i = hed[u.ind]; i ; i = nxt[i]) { int v = to[i]; if (dis[v] > dis[u.ind] + vall[i]) { dis[v] = dis[u.ind] + vall[i]; heap.push((node){dis[v], v}); } } } } void dfs(int u) { for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; dp[v] = max(dp[v], dp[u] + vall[i]); if (!(-- du[v])) dfs(v); } } int main() { n = read(); m = read(); x1 = read(); y1 = read(); x2 = read(); y2 = read(); for (int i = 1; i <= m; ++ i) { x[i] = read(); y[i] = read(); val[i] = read(); add(x[i], y[i], val[i]); add(y[i], x[i], val[i]); } dijkstra(x1, dis1); dijkstra(y1, dis2); dijkstra(x2, dis3); dijkstra(y2, dis4); memset(hed, 0, sizeof(hed)); cnt = 0; for (int i = 1; i <= m; ++ i) { if ((dis1[x[i]] + dis2[y[i]] + val[i] == dis1[y1]) || (dis1[y[i]] + dis2[x[i]] + val[i] == dis1[y1])) if ((dis3[x[i]] + dis4[y[i]] + val[i] == dis3[y2]) || (dis3[y[i]] + dis4[x[i]] + val[i] == dis3[y2])) { if (dis1[x[i]] > dis1[y[i]]) { add(y[i], x[i], val[i]); du[x[i]] ++; } else { add(x[i], y[i], val[i]); du[y[i]] ++; } } } for (int i = 1; i <= n; ++ i) if (!du[i]) dfs(i); for (int i = 1; i <= n; ++ i) ans = max(ans, dp[i]); printf("%d", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10246747.html
相关资源：JAVA上百实例源码以及开源项目