题解 P2149 【[SDOI2009]Elaxia的路线】
da_AA
2018-10-17 08:58:12
先不要脸的宣传一波[我的博客](https://www.cnblogs.com/wyxwyx/p/sdoi2009ela.html)
# Solution
不知道为啥泥萌要跑4遍最短路，我好像只跑了两遍。
要求最短路径的最长公共部分，我是先跑了一遍从$x_1$到$y_1$的最短路，然后把$x_1$到$y_1$最短路上的边打个标记。再跑一遍$x_2$到$y_2$的最短路，只不过这次的"边权"改为一对数：边的长度和边在第一次最短路中的长度。然后迪杰斯特拉跑的时候堆里先比较最短路长度，短的先出，如果最短路长度一样，在比较和之前重叠的长度，长的先出。
暂时通过了所有讨论中的hack数据。（应该是吧
代码也很好写啊，就是把普通的dij的`dis`换成一个自己写的结构体就行了啊。
# Code
```C++
#include <cstdio>
#include <cstring>
#include <queue>
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<node> 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;
}
```