QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#820478#4479. SlipperSGColinAC ✓433ms125076kbC++202.3kb2024-12-18 21:34:382024-12-18 21:34:38

Judging History

This is the latest submission verdict.

  • [2024-12-18 21:34:38]
  • Judged
  • Verdict: AC
  • Time: 433ms
  • Memory: 125076kb
  • [2024-12-18 21:34:38]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pli pair<ll, int>

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1000007
#define M 2000007

bool vis[N], visd[N];

ll dis[N];

int tot, n, k, p, hd[N], dep[N];

struct edge {int to, w, nxt;} e[M];

inline void add(int u, int v, int w) {
    e[++tot].to = v; e[tot].w = w; e[tot].nxt = hd[u]; hd[u] = tot;
    e[++tot].to = u; e[tot].w = w; e[tot].nxt = hd[v]; hd[v] = tot;
}

vector<int> s[N];

void dfs(int u, int fa, int d) {
    s[dep[u] = d].push_back(u);
    for (int i = hd[u], v; i; i = e[i].nxt)
        if ((v = e[i].to) != fa) dfs(v, u, d + 1);
}

priority_queue<pli, vector<pli>, greater<pli> > q;

inline void dij(int S) {
    dis[S] = 0; q.push(mp(0, S));
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue; vis[u] = true;
        for (int i = hd[u], v; i; i = e[i].nxt)
            if (dis[v = e[i].to] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                q.push(mp(dis[v], v));
            } 
        if (visd[dep[u]]) continue; visd[dep[u]] = true;
        if (dep[u] > k) 
            for (auto v : s[dep[u] - k])
                if (dis[v] > dis[u] + p) {
                    dis[v] = dis[u] + p; q.push(mp(dis[v], v));
                }
        if (dep[u] + k <= n)
            for (auto v : s[dep[u] + k])
                if (dis[v] > dis[u] + p) {
                    dis[v] = dis[u] + p; q.push(mp(dis[v], v));
                }
    }
}

inline void work() {
    tot = 0; n = rd();
    for (int i = 1; i <= n; ++i) {hd[i] = 0; s[i].clear();}
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(), w = rd();
        add(u, v, w);
    }
    k = rd(); p = rd();
    int s = rd(), t = rd();
    dfs(1, 0, 1);
    for (int i = 1; i <= n; ++i) dis[i] = 1e18, vis[i] = false, visd[i] = false;
    dij(s); printf("%lld\n", dis[t]);
} 

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 433ms
memory: 125076kb

input:

5
121753
103252 40559 325002
32674 51809 946614
18343 12099 625962
27677 48601 114048
11146 12478 906161
121147 77390 208299
39512 95642 154696
90603 43508 378490
4829 7818 191754
73699 31412 536840
106916 89894 374802
113739 90049 411062
113123 73246 740213
38047 120942 903325
51907 41500 822541
90...

output:

114128108
55207815
76620494
17377950755
67601

result:

ok 5 lines