Novice K/Advanced F: Graph Problem

Think non-simple paths, especially the ones that use the same edge several times.

Because a path does not need to be simple, at any node $$$u$$$, we can traverse the same edge twice in a row and return to $$$u$$$. Because of this, if we consider some path from $$$s$$$ to $$$t$$$ with path weight $$$c$$$, we can always augment the path weight by $$$2 \cdot w_i$$$ arbitrarily.

Let $$$g = \gcd(w_1, w_2, \dots, w_n)$$$. Then, using the ideas of Bezout's identity and the previous observation, all path weights in the set $$$\{c, 2g + c, \dots, 2(k-1) \cdot g + c\} \mod k$$$ are obtainable. Since $$$c \mid g$$$, only $$$c = 0$$$ and $$$c = g$$$ are important given they may form different sets.

If both $$$c$$$ values are obtainable, then the obtainable set of path weights is $$$\{0, g, \dots, g(k-1)\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, g)}$$$.

If only one $$$c$$$ is obtainable, the obtainable set of path weights is $$$\{c, 2g + c, \dots, 2(k-1)g + c\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, 2g)}$$$.

Define $$$W_i = \frac{w_i}{g}$$$. Let $$$W_i$$$ be the weights of a new graph. In this graph, we notice that the existence of an even path weight corresponds to $$$c = 0$$$ and the existence of an odd path weight corresponds to $$$c = g$$$. Calculating whether an odd and/or even path exists can be done using a BFS/DFS with two states per node $$$u$$$ (whether an odd/even path exists from $$$s$$$ to $$$u$$$), solving the problem in $$$\mathcal{O}(n)$$$.

If $$$g = 0$$$, then the answer is $$$1$$$. This must be handled manually to avoid division by $$$0$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
 
int n, m, qq, a, b;
ll k;
void solve() {
    cin >> n >> m >> k >> a >> b;
    a--, b--;
    ll g = 0;
    vector<pair<pi, ll>> edges(m);
    vector<vector<pi>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        edges[i] = {{--u, --v}, w};
        g = gcd(g, w);
    }
        
    if (g == 0) {
        cout << "1\n";
        return;
    }
 
    for (int i = 0; i < m; i++) {
        auto [p, w] = edges[i];
        auto [u, v] = p;
        adj[u].push_back({v, (w / g) & 1});
        adj[v].push_back({u, (w / g) & 1});
    }
 
    vector<vector<bool>> vis(2, vector<bool>(n));
    vis[0][a] = 1;
    queue<pi> q;
    q.push({0, a});
    while (!q.empty()) {
        auto [p, u] = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (!vis[(p + w) & 1][v]) {
                vis[(p + w) & 1][v] = 1;
                q.push({(p + w) & 1, v});
            }
        }
    }
 
    if (!vis[0][b] || !vis[1][b]) g *= 2;
    cout << k / gcd(g, k) << "\n";
}
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}