最短路变短了 (思维+反向djstrea)

题解：设有一条边x->y，数组dis1[i]表示从1到i的最短距离，dis2[i]表示从n到i的最短距离。

1 如果说将x->y反向之前没有经过x->y，但是反向后我经过了x,y说明找到了一个更优的路径，那么反向后的答案就是dis1[y]+dis2[x]+(x,y)，如果说反向后我没有经过

x->y，那也就是说x->y正向反向对dis[n]的结果没有影响喽。

2 如果说反向之前我经过了x->y，如果反向后没有经过x->y，那么此时的最短路也一定是大于等于dis1[n]的，因为会有一条新的路径长度处于dis1[n]和dis1[y]+dis2[x]+(x,y)之间。如果反向后经过了x->y，那么反向后的答案就是dis1[y]+dis2[x]+(x,y)。

综上所述，我们只需要判断dis1[y]+dis2[x]+(x,y)和dis1[n]的关系就行了。（看起来有点绕，仔细品品还是很有意思的）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=2e5+;

const ll INF=1e18+;

struct stu{

    ll a,b;

    bool friend operator<(const stu &x,const stu &y){

        return x.b>y.b;

    }

};

vector<stu>ve1[N];

vector<stu>ve2[N];

ll l[N],r[N],w[N];

ll n,m;

bool mark[N];

ll dis1[N],dis2[N];

void add1(ll x,ll y,ll weight){

    ve1[x].push_back({y,weight});

}

void add2(ll x,ll y,ll weight){

    ve2[x].push_back({y,weight});

}

void inll(){

    for(ll i=;i<=n;i++){

        dis1[i]=dis2[i]=INF;

    }

}

void djstrea1(ll s){

    priority_queue<stu>que;

    dis1[s]=;

    que.push({s,});

    while(que.size()){

       stu xx=que.top();

       que.pop();

       if(mark[xx.a]==) continue ;

       mark[xx.a]=;

       for(ll i=;i<ve1[xx.a].size();i++){

           ll dx=ve1[xx.a][i].a;

           ll dy=ve1[xx.a][i].b;

           if(mark[dx]==&&dis1[dx]>dis1[xx.a]+dy){

               dis1[dx]=dis1[xx.a]+dy;

               que.push({dx,dis1[dx]});

             }

         }

       }

}

void djstrea2(ll s){

    priority_queue<stu>que;

    dis2[s]=;

    que.push({s,});

    while(que.size()){

       stu xx=que.top();

       que.pop();

       if(mark[xx.a]==) continue ;

       mark[xx.a]=;

       for(ll i=;i<ve2[xx.a].size();i++){

           ll dx=ve2[xx.a][i].a;

           ll dy=ve2[xx.a][i].b;

           if(mark[dx]==&&dis2[dx]>dis2[xx.a]+dy){

               dis2[dx]=dis2[xx.a]+dy;

               que.push({dx,dis2[dx]});

             }

         }

       }

}

int main(){

    cin>>n>>m;

    inll();

    for(ll i=;i<=m;i++){

        ll x,y,z;

        cin>>x>>y>>z;

        l[i]=x;r[i]=y;w[i]=z;

        add1(x,y,z);

        add2(y,x,z);

    }

    djstrea1();

    memset(mark,,sizeof mark);

    djstrea2(n);

    ll t;

    cin>>t;

    while(t--){

        ll i;cin>>i;

        cout<<(dis1[n]>dis1[r[i]]+dis2[l[i]]+w[i]? "YES":"NO")<<endl;

    }

    return ;

 }

巴特西

最短路变短了 (思维+反向djstrea)

最新文章

热门文章