atcoder ABC61 C問題

ベルマンフォードを使わないと解けない問題だったので、解法をメモ

問題は、重み付き有効グラフで条件から、負のコストがあるのでダイクストラが使えず、ワーシャルフロイドもTLEに確実になるため使えない。そこで、ベルマンフォードを使いこの問題を解いていく。
まずベルマンフォードについてであるが基本的な方針はd[i]を始点から頂点iまでの最短距離とし、
for(int j;j <　頂点数;j++){
d[i] = min(d[j] + cost)
}
として最短距離を更新していく。雛形は下の通りである

int V;          //頂点数
int E;          //辺数
Edge[] map = new Edeg()[V];     //グラフの作成
int d[] = new int[V];       //最短距離


        for(int i = 0;i < m;i++){
            v[i]=new Edge();
            v[i].from=sc.nextInt();
            v[i].to=sc.nextInt();
            v[i].cost=sc.nextInt();     
        }

        dis = new long[n+1];
        Arrays.fill(dis, INF);              //初期化
        dis[1] = 0;

        long ans = 0;
        int count = 0;

        while(true){
            boolean update = false;
            for(int i = 0;i < E;i++){
                if(dis[v[i].from]+ v[i].cost < dis[v[i].to]){
                    dis[v[i].to]=dis[v[i].from]+v[i].cost;
                    updata= true;
                }
            }
            if(!update){                //更新なかったら抜ける
                break;
            }

        }

この問題では、「ゴールまでの最大値を求めよ」となっているので、あらかじめコストをマイナスで読み込むことでベルマンフォードを適用できるようにしている。また、閉路の検出のために、カウンターをつけ、ベルマンフォードでは、whileループがへんの数しか繰り返さないことを利用し、カウンターが辺の数になった時、ゴールまでの最短距離が更新されているか否かでinfかどうかを判定している。