CF567E 题解

题面

考虑如何一条边是必经之路：设 \(cntl_i\) 为从 \(s\) 到 \(i\) 走最短路的方案数，\(cntr_i\) 为从 \(i\) 到 \(t\) 最短路方案数。

由乘法原理，如果对于边 \(e_i=(u,v)\)，\(cnt_t=cnt_u\times cntr_v\)，则 \(e_i\) 是最短路上的必经边，输出 Yes 即可。

如果 \(cnt_u\times cntr_v=0\) 说明这条边不可能到达终点或不可达，输出 No。

否则设最短路长 \(d\)，从 \(s\) 到 \(i\) 最短路 \(disl_i\)，从 \(i\) 到 \(t\) 最短路 \(disr_i\)。

对于边 \(e_i=(u,v)\) 设 \(delta = w+disl_u+disr_v-d+1\)，若 \(w_i\leq dt\) 说明 \(w_i\) 再小也没用，输出 No。否则输出 \(\texttt{CAN } delta\)。

求终点相同的最短路和方案数只要建反图跑以原来终点为起点的最短路即可。

方案数在求最短路时可以和 dp 一样更新。

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

const int N = 1e5 + 5, p = 1e17 + 5;

ll dis[N], rdis[N], g[N], rg[N], n, m, s, t;
bool vis[N];
vector<pair<int, int>> e[N], e2[N];

void dij(ll *dis, ll *g, vector<pair<int, int>> *e, int s)
{
    using pii = pair<ll, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    memset(dis, 0x3f, sizeof ::dis);
    memset(vis, 0, sizeof vis);
    dis[s] = 0; 
    g[s] = 1;
    while(q.size())
    {
        int t = q.top().second; q.pop();
        if(vis[t]) continue;
        vis[t] = 1;
        for(auto [i, w] : e[t])
        {
            if(dis[i] < dis[t] + w) continue;
            if(dis[i] == dis[t] + w)
            {
                g[i] = (g[i] + g[t]) % p;
                continue;
            }
            g[i] = g[t];
            dis[i] = dis[t] + w;
            q.push({dis[i], i});
        }
    }
}

int u[N], v[N], w[N];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z; cin >> x >> y >> z;
        e[x].push_back({y, z});
        e2[y].push_back({x, z});
        u[i] = x, v[i] = y, w[i] = z;
    }
    dij(dis, g, e, s);
    dij(rdis, rg, e2, t);
    ll d = dis[t];
    for(int i = 1; i <= m; i ++)
    {
        if(dis[u[i]] + w[i] + rdis[v[i]] == d)
        {
            if((__int128)g[u[i]] * rg[v[i]] % p != g[t])
            {
                if(w[i] == 1) cout << "NO\n";
                else cout << "CAN " << 1 << "\n";
            }
            else cout << "YES\n";
        }
        else
        {
            ll dt = dis[u[i]] + w[i] + rdis[v[i]] - d;
            if(w[i] <= dt + 1) cout << "NO\n";
            else cout << "CAN " << dt + 1 << "\n";
        }
    }

    return 0;
}