ABC061-D Score Attack

リンク

https://atcoder.jp/contests/abc061/tasks/abc061_d

問題

N頂点M辺の重み付き有向グラフが与えられる。

プレイヤーは始め0ポイントからスタートし、頂点AiからBiに移動するとCiポイントを得る。

頂点１から頂点Nに移動することを考える。頂点Nに達した時のみゲームをやめることが出来る。最善を尽くした時、ポイントが幾つになるか求めよ。ただ、いくらでも大きく出来る場合はinfを出力せよ。

考えたこと

最短経路を求めるアルゴリズムを上手くこの問題に適用したい→ポイントの符号を入れ替えることで最短経路問題に帰着する！！というのがこの問題のポイント。

最終的に得られる最短経路の値をマイナス倍したのが答えとなる。

ただ、これだけでは足りなく、得点がinfになる場合も考えないといけない。この時符号が反転しているので、頂点1から頂点Nに負の閉路がないかどうか調べることで判定出来る。

これらの実装は蟻本のBellman-Ford法のページに詳しく書いてあるので僕はそこで勉強しました。

実装

#include <iostream>
using namespace std;
typedef long long ll;

struct Edge{
	ll cost;
	int from,to;
	Edge(){}
	Edge(int from,int to,ll cost): from(from),to(to),cost(cost){}
};

int n,m;
Edge e[2005];
ll d[1005];

bool bellman_ford(){
	for(int i=0;i<1005;i++){
		d[i]=1e18;
	}
	d[0]=0;
	for(int i=0;i<2*n;i++){
		for(int j=0;j<m;j++){
			if(d[e[j].from]!=1e18 && d[e[j].to]>d[e[j].from]+e[j].cost){
				d[e[j].to]=d[e[j].from]+e[j].cost;
				if(i>=n-1&&e[j].to==n-1) return true;
			}
		}
	}
	return false;
}

int main(){
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int a,b; ll c;
		cin >> a >> b >> c;
		e[i]=Edge(a-1,b-1,-c);
	}
	if(bellman_ford()){
		cout << "inf" << endl;
	}
	else{
		cout << -d[n-1] << endl;
	}
}