To be better

题解 P2149 【[SDOI2009]Elaxia的路线】

2018-10-17 08:58:12


先不要脸的宣传一波我的博客

Solution

不知道为啥泥萌要跑4遍最短路,我好像只跑了两遍。

要求最短路径的最长公共部分,我是先跑了一遍从 $x_1$ 到 $y_1$ 的最短路,然后把 $x_1$ 到 $y_1$ 最短路上的边打个标记。再跑一遍 $x_2$ 到 $y_2$ 的最短路,只不过这次的"边权"改为一对数:边的长度和边在第一次最短路中的长度。然后迪杰斯特拉跑的时候堆里先比较最短路长度,短的先出,如果最短路长度一样,在比较和之前重叠的长度,长的先出。

暂时通过了所有讨论中的hack数据。(应该是吧

代码也很好写啊,就是把普通的dij的dis换成一个自己写的结构体就行了啊。

Code

#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;
}