AtCoder ABC #137 : E - Coins Respawn

Dまでは順調だったのにそこからミスが多すぎた。
https://atcoder.jp/contests/abc137/tasks/abc137_e

問題

N頂点M辺の有向グラフがある。
各辺にはスコアC[v]が設定されており、通るたびにそのスコアC[v]が得られる。
1番の頂点からN番の頂点に辺に沿って移動することを考える。

N番の頂点に到着した場合、そこで移動を止めるか、さらに続けるかは選択できるとする。
移動時のペナルティPが設定されており、移動止めたとき、そこまでT回辺に沿った移動を行うと、取得スコアがT*Pだけ減少する。

N番の頂点で移動を止めるときの最高取得スコアを求めよ。

解法

1回移動するとペナルティでPだけスコアを失うので、最初から各辺のスコアをC[v]-Pだと考えておけばよい。
この問題は負閉路検出とみなしてベルマンフォード法を使うこともできるのだが、以下では別解法を紹介。

無限にスコアを稼げるのは、１周まわってペナルティを考慮してもスコアをプラスできるような閉路があり、かつその閉路からN番の頂点に移動できる場合である。

逆にそのような閉路が無ければ、最高取得スコアは移動回数N-1回以下になるはずである。
そこで、2N回程度辺を遷移し、各頂点に至る最高スコアを求めよう。
N回目以降の遷移で、どこかの頂点でスコア最大値の更新が発生した場合、その時点で閉路によるスコア増加が可能と判断し、以降その頂点のスコアを∞とみなせばよい。

int N,M,P;
ll from[2500],to[2500];

vector<pair<int,int>> E[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
	}
	
	FOR(i,N) from[i]=-(1LL<<60);
	from[0]=0;
	ll ma=-1LL<<60;
	FOR(i,10000) {
		FOR(j,N) to[j]=from[j];
		FOR(x,N) if(from[x]>-(1LL<<60)) FORR(e,E[x]) {
			to[e.first]=max(to[e.first],from[x]+e.second-P);
			if(i>=5100&&to[e.first]>from[e.first]) to[e.first]=1LL<<60;
		}
		
		ma=max(ma,to[N-1]);
		swap(from,to);
	}
	ma=max(ma,0LL);
	if(ma>=1LL<<59) ma=-1;
	cout<<ma<<endl;
	
	
}

まとめ

しょうもないミスでタイムロス+4WAがもったいない。