fork download

copy

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
#define mp make_pair
#define pb(x) push_back(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()
 
#define INF 2123456789
#define IINF 9123456789123456789
 
void use_cio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
template <typename... Args>
void dbg(Args... args) {
    ((cout << args << " "), ...);
    cout << endl;
}
//--------------------------------------------------//
int n, q;
vector<pii> adj[100010];
int chk[100010], dep[100010], par[100010];
int p[100010][30];
ll dist1[100010], dist2[100010], tot_dist, conn[100010];
vi cycle;
void dfs(int cur, int par) {
    chk[cur] = par;
    for (auto [nxt, w] : adj[cur]) {
        if (nxt == par) continue;
        if (chk[nxt] != 0) {
            tot_dist = dist1[cur] + w - dist1[nxt];
            while (1) {
                cycle.push_back(cur);
                cur = chk[cur];
                if (cur == nxt || cur == -1) break;
            }
            cycle.push_back(nxt);
            return;
        }
        dist1[nxt] = dist1[cur] + w;
        dfs(nxt, cur);
        if (!cycle.empty()) return;
    }
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    int lg = 1;
    for (lg = 1; (1 << lg) <= dep[u]; lg++)
        ;
    lg -= 1;
    for (int i = lg; i >= 0; i--) {
        if (dep[u] - (1 << i) >= dep[v]) {
            u = p[u][i];
        }
    }
    if (u == v) {
        return u;
    } else {
        for (int i = lg; i >= 0; i--) {
            if (p[u][i] != 0 && p[u][i] != p[v][i]) {
                u = p[u][i];
                v = p[v][i];
            }
        }
        return par[u];
    }
}
 
void solve() {
    rep(i, 100010) adj[i].clear(), dep[i] = par[i] = chk[i] = dist1[i] = dist2[i] = conn[i] = 0;
    memset(p, 0, sizeof(p));
    cycle.clear();
    tot_dist = 0;
 
    cin >> n >> q;
    rep(i, n) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, -1);
    memset(chk, 0, sizeof(chk));
    queue<int> que;
    for (auto x : cycle) {
        dep[x] = 0;
        chk[x] = 1;
        par[x] = 0;
        conn[x] = x;
        que.push(x);
    }
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (auto [y, w] : adj[x]) {
            if (!chk[y]) {
                dep[y] = dep[x] + 1;
                chk[y] = 1;
                par[y] = x;
                conn[y] = conn[x];
                dist2[y] = dist2[x] + w;
                que.push(y);
            }
        }
    }
    for (int i = 1; i <= n; i++) p[i][0] = par[i];
    for (int j = 1; (1 << j) < n; j++) {
        for (int i = 1; i <= n; i++) {
            if (p[i][j - 1] != 0) {
                p[i][j] = p[p[i][j - 1]][j - 1];
            }
        }
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        if (conn[u] != conn[v]) {
            ll ans = dist2[u] + dist2[v];
            u = conn[u], v = conn[v];
            ll dd = abs(dist1[u] - dist1[v]);
            dd = min(dd, tot_dist - dd);
            cout << ans + dd << "\n";
        } else {
            int foo = lca(u, v);
            cout << dist2[u] + dist2[v] - 2 * dist2[foo] << "\n";
        }
    }
}
int main() {
    use_cio();
    int tc;
    cin >> tc;
    while (tc--) solve();
}

prog.cpp: In function ‘void dbg(Args ...)’:
prog.cpp:25:29: warning: fold-expressions only available with -std=c++1z or -std=gnu++1z
     ((cout << args << " "), ...);
                             ^~~
prog.cpp: In function ‘void dfs(int, int)’:
prog.cpp:37:15: error: expected unqualified-id before ‘[’ token
     for (auto [nxt, w] : adj[cur]) {
               ^
prog.cpp:37:15: error: expected ‘;’ before ‘[’ token
prog.cpp:37:16: error: ‘nxt’ was not declared in this scope
     for (auto [nxt, w] : adj[cur]) {
                ^~~
prog.cpp:37:21: error: ‘w’ was not declared in this scope
     for (auto [nxt, w] : adj[cur]) {
                     ^
prog.cpp: In lambda function:
prog.cpp:37:24: error: expected ‘{’ before ‘:’ token
     for (auto [nxt, w] : adj[cur]) {
                        ^
prog.cpp: In function ‘void dfs(int, int)’:
prog.cpp:37:24: error: expected ‘;’ before ‘:’ token
prog.cpp:37:24: error: expected primary-expression before ‘:’ token
prog.cpp:37:24: error: expected ‘)’ before ‘:’ token
prog.cpp:37:24: error: expected primary-expression before ‘:’ token
prog.cpp: In function ‘void solve()’:
prog.cpp:106:19: error: expected unqualified-id before ‘[’ token
         for (auto [y, w] : adj[x]) {
                   ^
prog.cpp:106:19: error: expected ‘;’ before ‘[’ token
prog.cpp:106:20: error: ‘y’ was not declared in this scope
         for (auto [y, w] : adj[x]) {
                    ^
prog.cpp:106:23: error: ‘w’ was not declared in this scope
         for (auto [y, w] : adj[x]) {
                       ^
prog.cpp: In lambda function:
prog.cpp:106:26: error: expected ‘{’ before ‘:’ token
         for (auto [y, w] : adj[x]) {
                          ^
prog.cpp: In function ‘void solve()’:
prog.cpp:106:26: error: expected ‘;’ before ‘:’ token
prog.cpp:106:26: error: expected primary-expression before ‘:’ token
prog.cpp:106:26: error: expected ‘)’ before ‘:’ token
prog.cpp:106:26: error: expected primary-expression before ‘:’ token

Standard output is empty