NC5026D

题意

一张连通有向图，另一条边反向，是否缩短了1到n的最短路？
保证开始给定的图从城市1可以到达城市n，若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短。

思路

数据范围较大，最原始的暴力每次djikstra一遍肯定是TLE的，于是思考预处理，预先djiksra一遍。
每次反向一条边和没反向有什么区别呢？想到直接在原图上加一条反向边，原来的边不管他不影响结果。
这时候画个图

当我们反转2←4这条路，使得其变为2→4，新的最短路路径的算法为 1到2的距离 + 4到2的距离 + 4到5的距离。
我们将这个模型一般化，就是 和原先的最短路比较即可。
问题是我们知道了1到i的最短路还不知道j到n的最短路呢，难道我们要求所有两点间的最短路吗？那样一定会TLE，我们的终点已经确定了的情况，我们只需要反向建图，再将n作为起点在进行一次djikstra即可。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const ll INF  = 0x3f3f3f3f3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

int u[2*N],v[2*N],c[2*N];

struct edge{int to,cost;};
ll n,m,d[N],e[N];
vector<edge>G[N];
vector<edge>F[N];

void Dji1(const int& s,const int& V){
    priority_queue<P,vector<P>,greater<P> >q;
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    q.push({0,s});
    while(!q.empty()){
        P t=q.top();q.pop();
        ll v=t.se;
        if(d[v]<t.fi) continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                q.push({d[e.to],e.to});
            }
        }
    }
}

void Dji2(const int& s,const int& V){
    priority_queue<P,vector<P>,greater<P> >q;
    memset(e,0x3f,sizeof(e));
    e[s]=0;
    q.push({0,s});
    while(!q.empty()){
        P t=q.top();q.pop();
        ll v=t.se;
        if(e[v]<t.fi) continue;
        for(int i=0;i<F[v].size();i++){
            edge k=F[v][i];
            if(e[k.to]>e[v]+k.cost){
                e[k.to]=e[v]+k.cost;
                q.push({e[k.to],k.to});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>c[i];
        G[u[i]].push_back({v[i],c[i]});
        F[v[i]].push_back({u[i],c[i]});
    }
    Dji1(1,n);
    Dji2(n,n);
    int T;cin>>T;
    while(T--){
        int x;
        cin>>x;
        int i=u[x],j=v[x],p=c[x];
        ll temp=d[j]+p+e[i];
        if(temp<d[n]) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}