Naomi's notebook

Naomi's notebook

最長経路問題byベルマンフォード(ABC061D - Score Attack)

atcoder.jp

問題を見てダイクストラ法ですかねと思い、ダイクストラ実装…してから気づいたけどよく考えたら最長経路問題だった。部分構造最適性が成立していないのでダイクストラ法みたいに計算量少なくは出来なかった…(色々考えた)

辺の値全てに-1をかけると最短経路問題にできるので、負の辺がある有向グラフの最短経路問題を解くのに使われるベルマンフォード法が思いつきますね(負の閉路がある場合も検知はできる)。計算量はO(NM)\leqq 2000,000
何気にダイクストラの問題ばっかり解いていて、ベルマンフォードの実装をしたことが少なくともn年はなかったため、wikipediaとにらめっこして書いた。

subtask_1_23.txt, subtask_1_25.txt, subtask_1_27.txtでWA。これはベルマンフォード法のwikipediaに載っているやつは0からN-1にいく経路上にないところにある負の閉路も検出してしまうからで、負閉路検出を改良すればACできる。

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long
struct Bellman_Ford{ //たどり着けないときはLLINF、負の閉路を持つときは-LLINFを返す。
    int N;
    long long int *d;
    int *pre;
    bool *negative;
    vector< pair< pair<int,int> , int> > edges;
    Bellman_Ford(int N) : N(N){
        d=new long long int[N];
        pre=new int[N];
        negative=new bool[N];
        rep(i,N){
            d[i]=LLINF;
            pre[i]=-1;
            negative[i]=false;
        }
    }
    void push_nondir(int a,int b, int c){
        edges.pb( mp( mp(a,b),c) );
        edges.pb( mp( mp(b,a),c) );
    }
    void push_dir(int a,int b, int c){
        edges.pb( mp( mp(a,b) ,c) );
    }
    long long int solve(int start, int end){
        d[start]=0;
        rep(i,N-1){
            rep(j,edges.size()){
                int from=edges[j].first.first;int to=edges[j].first.second;int cost=edges[j].second;
                if(d[to]>d[from]+cost){
                    d[to]=d[from]+cost;
                    pre[to]=from;
                }
            }
        }
        //startからendにいく回路の中に負の重みの閉路がある?
        rep(i,N){
            rep(j,edges.size()){
                int from=edges[j].first.first;int to=edges[j].first.second;int cost=edges[j].second;
                if(d[to]>d[from]+cost){
                    d[to]=d[from]+cost;
                    negative[to]=true;
                }
                if(negative[from])negative[to]=true;
            }
        }
        if(negative[end]) return -LLINF;
        else return d[end];
    }
    bool anywhere_negativeC(){//do after solve()
        rep(i,edges.size()){
            int from=edges[i].first.first;int to=edges[i].first.second;int cost=edges[i].second;
            if(d[to]>d[from]+cost)return true;
        }
        return false;
    }
    void free_BF(){
        delete[] d;
        delete[] pre;
        delete[] negative;
    }
    
};
int main(void){
    int N,M;
    scanf("%d %d",&N,&M);
    Bellman_Ford BF(N);
    rep(i,M){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        a--;b--;
        BF.push_dir(a,b,-c);
    }
    long long int ans=BF.solve(0,N-1);
    if(ans==-LLINF)printf("inf\n");
    else printf("%lld\n",-ans);
    BF.free_BF();
}