牛客练习赛61 - D 最短路变短了

传送门：牛客练习赛61 - D

思路分析

正向反向跑一次最短路得到两个数组d1，d2
那么对于每次询问$u,v,w$只需要判断$d1[v]+d2[u]+w<d1[n]$是否成立就行了
如果还需要判断最短路是否不变的话怎么办呢？
将最短路的边加入一个无向图中，通过Tarjan找出所有的桥
如果是桥的话，也就是必经边，必不可能到达终点

样例输入

3 4 
1 2 100 
2 3 100 
3 1 100 
2 1 1 
2 
1
4

样例输出

NO
YES

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long
 
using namespace std;
 
const int INF = 1e18;
const int N=1e6+10;
 
vector<pair<int,int>>e1[N],e2[N];
 
struct node {
    int v,w,next;
} e[N];
 
struct edge {
    int u,v,w;
} s[N];
 
int cnt,head[N],d1[N],d2[N],vis[N],id[N],dfn[N],low[N],vistime,must[N];
int n,m;
 
void add(int u,int v,int w,int i) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    id[cnt]=i;
    head[u]=cnt;
}
 
void dij(int s,int *dis,vector<pair<int,int>> *edge) {
    for(int i=0; i<=n; i++) {
        dis[i]=INF;
        vis[i]=0;
    }
    dis[s]=0;
    priority_queue<pair<int,int> > q;
    q.push(make_pair(-dis[s],s));
    while(!q.empty()) {
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:edge[u]) {
            int v=i.fi;
            int w=i.se;
            if(!vis[v]&&dis[v]>dis[u]+w) {
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}
 
void tarjan(int u,int fa) {
    dfn[u]=low[u]=++vistime;
    for (int i=head[u]; i; i=e[i].next) {
        int v=e[i].v;
        if (!dfn[v]) {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>dfn[u]){
                must[id[i]]=1; //桥
            }
        } else if(v!=fa)
            low[u]=min(low[u],dfn[v]);
    }
}
 
 
signed main() {
 
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
 
    cnt=1;
    mem(head,0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        s[i].u=u;
        s[i].v=v;
        s[i].w=w;
        e1[u].push_back(mp(v,w));
        e2[v].push_back(mp(u,w));
    }
    dij(1,d1,e1);
    dij(n,d2,e2);
    for(int i=1; i<=m; i++) {
        int u=s[i].u;
        int v=s[i].v;
        int w=s[i].w;
        if(d1[u]+d2[v]+w==d1[n]) {
            add(u,v,w,i);
            add(v,u,w,i);
        }
    }
    tarjan(1,1);
    int q;
    cin>>q;
    while(q--) {
        int x;
        cin>>x;
        int u=s[x].u;
        int v=s[x].v;
        int w=s[x].w;
        if(d1[v]+d2[u]+w<d1[n] && !must[x]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
 
 
 
    return 0;
}