Description
Solution
要求最短路径的最长公共部分，我是先跑了一遍从\(x_1\)到\(y_1\)的最短路，然后把\(x_1\)到\(y_1\)最短路上的边染色。再跑一遍\(x_2\)到\(y_2\)的最短路，只不过这次的"边权"改为一对数：边的长度和边在第一次最短路中的长度。然后迪杰斯特拉跑的时候堆里先比较最短路长度，短的先出，如果最短路长度一样，在比较和之前重叠的长度，长的先出。
Code
#include#include #include typedef long long ll;const int N = 1510;const int M = N * (N - 1);struct state { int x, y; state(int x = 0, int y = 0) : x(x), y(y) {} bool operator>(const state& a) const { return x == a.x ? y < a.y : x > a.x; } state operator+(const state& a) const { return state(x + a.x, y + a.y); } bool operator==(const state& a) const { return x == a.x && y == a.y; } bool operator<(const state& a) const { return !(*this == a || *this > a); }} dis[N], w[M];int vis[N], hd[N], to[M], nxt[M], cnt = 1, n, m, fl[M];inline void adde(int x, int y, int z) { to[++cnt] = y; nxt[cnt] = hd[x]; w[cnt].x = z; hd[x] = cnt;}struct node { int p; state d; node(int p = 0, state d = state(0, 0)) : p(p), d(d) {} bool operator<(const node& x) const { return d > x.d; }};std::priority_queue q;void dij(int s) { for (int i = 1; i <= n; ++i) dis[i] = state(0x3f3f3f3f, 0), vis[i] = 0; q.push(node(s, dis[s] = state(0, 0))); while (!q.empty()) { node x = q.top(); q.pop(); if (vis[x.p]) continue; vis[x.p] = 1; for (int i = hd[x.p]; i; i = nxt[i]) if (!vis[to[i]]) { if (dis[to[i]] > x.d + w[i]) q.push(node(to[i], dis[to[i]] = x.d + w[i])); } }}void dfs(int x) { // printf("%d\n", x); for (int i = hd[x]; i; i = nxt[i]) { if (dis[to[i]] + w[i] == dis[x]) { w[i].y += w[i].x; w[i ^ 1].y += w[i].x; dfs(to[i]); } }}int main() { scanf("%d%d", &n, &m); int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); for (int i = 1, x, y, z; i <= m; ++i) { scanf("%d%d%d", &x, &y, &z); adde(x, y, z); adde(y, x, z); } dij(x1); // printf("%d %d\n", dis[y1].x, dis[y1].y); dfs(y1); dij(x2); printf("%d\n", dis[y2].y); return 0;}