专栏首页数据结构与算法cf567E. President and Roads(最短路计数)

cf567E. President and Roads(最短路计数)

题意

题目链接

给出一张有向图,以及起点终点,判断每条边的状态:

  1. 是否一定在最短路上,是的话输出'YES'
  2. 如果不在最短路上,最少减去多少权值会使其在最短路上,如果减去后的权值\(< 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P3246 [HNOI2016]序列(离线 差分 树状数组)

    也就是我们需要解决这么一个问题:两个操作, 矩形加矩形求和,而且前者都在后者的前面执行

    attack
  • cf19E. Fairy(奇环 二分图染色)

    非常有思维含量的一道题,队爷的论文里介绍了一种\(N \sqrt{N}\)的暴力然鹅看不懂。。

    attack
  • 洛谷P1351 联合权值(树形dp)

    attack
  • POJ-2406-Power Strings

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstring> using namespa...

    f_zyj
  • 去噪:用于验证码图片识别的类续(C#代码)

    用户1258909
  • Android必知必会 - RecyclerView 恢复上次滚动位置

    记录 RecyclerView 滚动位置并恢复是一个很常见的需求,通常需要精准恢复到上次的位置。

    他叫自己MR.张
  • 一个开源的营销自动化软件——Mautic

    营销自动化这个东西已经出现了有十多年来,最近两年又不断被提起,大部分是厂家的内容,可以看看近几年的百度指数:

    GA小站
  • 1588: 合并果子

    渔父歌
  • 国科大CVPR 2020论文:自监督学习新方法,让数据更复杂的视频表征学习性能大提升

    近年来,自监督表征学习由于无需人工标注,特征较好的泛化性等优势受到了越来越多的关注,并不断有研究在图像、语言等领域取得了较大进展。本论文则立足于数据形式更为复杂...

    新智元
  • 2013-2-22 新项目有点慢

    U项目上线时间定在2月28日

    lilugirl

扫码关注云+社区

领取腾讯云代金券