cf567E. President and Roads(最短路计数)
程序员文章站
2022-07-02 15:45:42
题意 "题目链接" 给出一张有向图,以及起点终点,判断每条边的状态: 1. 是否一定在最短路上,是的话输出'YES' 2. 如果不在最短路上,最少减去多少权值会使其在最短路上,如果减去后的权值$ define Pair pair define MP make_pair define fi first ......
题意
给出一张有向图,以及起点终点,判断每条边的状态:
是否一定在最短路上,是的话输出'yes'
如果不在最短路上,最少减去多少权值会使其在最短路上,如果减去后的权值\(< 1\),输出'no',否则输出'can + 花费'
sol
考察对最短路的理解。
首先确定哪些边一定在最短路上,一个条件是 从起点到该点的最短路 + 边权 + 从该点到终点的最短路 = 从起点到终点的最短路
同时还要满足没有别的边可以代替这条边,可以用tarjan求一下桥。当然也可以直接用最短路条数判
这样的话正反跑一边dijkstra求出最短路以及最短路径的条数,判断一下即可
#include<bits/stdc++.h> #define pair pair<ll, int> #define mp make_pair #define fi first #define se second #define ll long long using namespace std; const int maxn = 2e5 + 10; const ll inf = 1e18 + 10; const ll mod1 = 2860486313ll, mod2 = 1500450271ll; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, s, t, vis[maxn]; ll f[maxn], g[maxn], f2[maxn], g2[maxn]; ll dis[maxn], rdis[maxn]; vector<pair> v[maxn], t[maxn]; struct edge { int u, v; ll w;} e[maxn]; ll add(ll x, ll y, ll mod) { return (x + y >= mod ? x + y - mod : x + y); } void dij(int s, ll *d, ll *f, ll *f2, int opt) { priority_queue<pair> q; q.push(mp(0, s)); for(int i = 1; i <= n; i++) d[i] = inf; d[s] = 0; f[s] = f2[s] = 1; memset(vis, 0, sizeof(vis)); while(!q.empty()) { if(vis[q.top().se]) {q.pop(); continue;} int p = q.top().se; q.pop(); vis[p] = 1; vector<pair> *e = (opt == 1 ? v + p : t + p); for(int i = 0; i < e -> size(); i++) { int to = (*e)[i].fi, w = (*e)[i].se; if(d[to] > d[p] + w) d[to] = d[p] + w, f[to] = f[p], f2[to] = f2[p], q.push(mp(-d[to], to)); else if(d[to] == d[p] + w) f[to] = add(f[to], f[p], mod1), f2[to] = add(f2[to], f2[p], mod2); } } } signed main() { n = read(); m = read(); s = read(); t = read(); for(int i = 1; i <= m; i++) { int x = read(), y = read(), z = read(); e[i] = (edge) {x, y, z}; v[x].push_back(mp(y, z)); t[y].push_back(mp(x, z)); } dij(s, dis, f, f2, 1); dij(t, rdis, g, g2, 2); for(int i = 1; i <= m; i++) { int x = e[i].u, y = e[i].v;ll w = e[i].w; if((dis[x] + w + rdis[y] == dis[t]) && (1ll * f[x] * g[y] % mod1 == f[t]) && (1ll * f2[x] * g2[y] % mod2 == f2[t])) puts("yes"); else { ll ned = dis[t] - dis[x] - rdis[y] ; if(ned <= 1) puts("no"); else printf("can %i64d\n", w - ned + 1); } } return 0; }
上一篇: 缓存雪崩原因及解决方案
下一篇: 浏览器底层渲染机制