Description

Solution

65分做法

先求出每个点到\(1\)号点的最短路，记为\(d[i]\)。然后按照海拔从大到小依次加边，并查集维护每个连通块中\(d[i]\)的最小值，并同时回答询问。

70分做法

形态为树，以\(1\)为根，询问时向上倍增。

满分做法

结合上两种做法，按照海拔建出Kruskal重构树，求出每个点子树中的\(d[i]\)最小值，询问时向上倍增。

Code

#include 
    
     #include 
     
      #include 
      
       struct Node {    int u, v, l, a;    bool operator < (const Node & rhs) const {        return a > rhs.a;    }} a[400002];struct Edge {    int u, v, w, nxt;} e[800002];struct Pair {    int x, y;    bool operator < (const Pair & rhs) const {        return x > rhs.x;    }};std::priority_queue
       
         q;int head[200002], vis[200002], d[400002], v[400002], f[400002][20], fa[400002], tot, n, m;int read() {    int x = 0; char c = getchar();    while (c < '0' || c > '9') c = getchar();    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();    return x;}void adde(int u, int v, int w) {    e[++tot].nxt = head[u], head[u] = tot, e[tot].v = v, e[tot].w = w;}int find(int x) {    return x == fa[x] ? x : fa[x] = find(fa[x]);}void dijkstra() {    while (!q.empty()) q.pop();    for (int i = 2; i <= n; ++i) d[i] = 0x7fffffff;    q.push((Pair){0, 1});    int cnt = 0;    while (!q.empty()) {        int u = q.top().y;        q.pop();        if (vis[u]) continue;        vis[u] = 1;        if (++cnt == n) return;        for (int i = head[u]; i; i = e[i].nxt)            if (d[e[i].v] > d[u] + e[i].w)                d[e[i].v] = d[u] + e[i].w, q.push((Pair){d[e[i].v], e[i].v});    }}int main() {    int T = read();    while (T--) {        n = read(), m = read(), tot = 0;        for (int i = 1; i <= n; ++i) head[i] = vis[i] = f[i][0] = 0, fa[i] = i;        for (int i = 1; i <= m; ++i) {            a[i].u = read(), a[i].v = read(), a[i].l = read(), a[i].a = read();            adde(a[i].u, a[i].v, a[i].l), adde(a[i].v, a[i].u, a[i].l);        }        dijkstra();        std::sort(a + 1, a + m + 1);        int cnt = n;        for (int i = 1; i <= m; ++i) {            int x = find(a[i].u), y = find(a[i].v);            if (fa[x] == fa[y]) continue;            f[x][0] = f[y][0] = ++cnt, v[cnt] = a[i].a, d[cnt] = std::min(d[x], d[y]);            fa[x] = fa[y] = fa[cnt] = cnt, f[cnt][0] = 0;        }        for (int i = cnt; i; --i)            for (int j = 1; j <= 18; ++j)                f[i][j] = f[f[i][j - 1]][j - 1];        int q = read(), k = read(), s = read(), ans = 0;        while (q--) {            int x = (read() + k * ans - 1) % n + 1, y = (read() + k * ans) % (s + 1);            for (int i = 18; ~i; --i)                if (v[f[x][i]] > y) x = f[x][i];            printf("%d\n", ans = d[x]);        }    }    return 0;}