牛客寒假训练营3 B 处女座的比赛资格(拓扑排序+最短路）

题目链接

这个题，一眼看上去就是最短路的题，边权有负环显然不能用dij，然后出题人又卡了spfa，，那怎么办的想点办法啊，好像还有一个拓扑排序可以求最短路吧，这时候正解就已经得到了，就是拓扑排序求最短路。

在求拓扑序的时候，每次入队时，将这个入队的点所拓展出来的点都进行松弛操作，就可以啦，复杂度O(E+V)，后面的判断还要注意一下。就做完啦。

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define ll __int64

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

//head

vector<pair<int,pair<LL,pair<LL,LL> > > >v[100001];

LL disa[100001],disb[100001];

int inq[100001];

int du[100001],dd[100001];

int main(){

    ios::sync_with_stdio(false);

    int tt;

    for(cin>>tt;tt;tt--){

        int n,m;

        cin>>n>>m;

        for(int i=1;i<=n;i++)v[i].clear(),disa[i]=1e18,disb[i]=1e18,inq[i]=du[i]=dd[i]=0;

        disa[1]=disb[1]=0;

        for(int i=1;i<=m;i++){

            int s,t;

            LL c,cb,jff;

            cin>>s>>t>>c>>cb>>jff;

            v[s].pb({t,{c,{-cb,-jff}}});

            du[t]++;

            dd[t]++;

        }

        queue<int>p,q;

        while(!p.empty())p.pop();

        while(!q.empty())q.pop();

        for(int i=1;i<=n;i++){

            if(!du[i]){

                p.push(i);

                for(auto k:v[i]){

                    if(disa[k.fi]>disa[i]+k.se.fi+k.se.se.fi){

                        disa[k.fi]=disa[i]+k.se.fi+k.se.se.fi;

                    }

                }

            }

            if(!dd[i]){

                q.push(i);

                for(auto k:v[i]){

                    if(disb[k.fi]>disb[i]+k.se.fi+k.se.se.se){

                        disb[k.fi]=disb[i]+k.se.fi+k.se.se.se;

                        //cout<<k.fi<<' '<<disb[k.fi]<<endl;

                    }

                }

            }

        }

        while(!p.empty()){

            int now=p.front();

            p.pop();

            for(auto k:v[now]){

                --du[k.fi];

                if(!du[k.fi]){

                    p.push(k.fi);

                    for(auto kk:v[k.fi]){

                        if(disa[kk.fi]>disa[k.fi]+kk.se.fi+kk.se.se.fi){

                            disa[kk.fi]=disa[k.fi]+kk.se.fi+kk.se.se.fi;

                        }

                    }

                }

            }

        }

        while(!q.empty()){

            int now=q.front();

            q.pop();

            for(auto k:v[now]){

                --dd[k.fi];

                if(!dd[k.fi]){

                    q.push(k.fi);

                    for(auto kk:v[k.fi]){

                        if(disb[kk.fi]>disb[k.fi]+kk.se.fi+kk.se.se.se){

                            disb[kk.fi]=disb[k.fi]+kk.se.fi+kk.se.se.se;

                        }

                    }

                }

            }

        }

        swap(disa[n],disb[n]);

        disa[n]=max(disa[n],0ll);

        if(disa[n]==0&&disb[n]<=0){

            cout<<"oof!!!\n";

        }else {

            if(disb[n]<=0){

                cout<<"cnznb!!!\n";

                cout<<disa[n]<<endl;

            }else{

                if(disb[n]>disa[n]){

                    cout<<"rip!!!\n";

                    cout<<disb[n]-disa[n]<<endl;

                }else{

                    cout<<"cnznb!!!\n";

                    cout<<disa[n]-disb[n]<<endl;

                }

            }

        }

    }

    return 0;

}

巴特西

牛客寒假训练营3 B 处女座的比赛资格(拓扑排序+最短路）

最新文章

热门文章