ABC137-E Coins Respawn

リンク

https://atcoder.jp/contests/abc137/tasks/abc137_e

問題

N頂点M辺の有効グラフが与えられる。辺を通るとCiのコインが得られる。このコインは辺を通った後何度も復活する。頂点Nに到達した時ゲームを辞めることが出来る。ただし、ゲームを終了する際に、ゲーム開始からの経過時間をT分としてT*P枚のコインの支払いが要求されます。持っているコインがT*P枚以下の時は、代わりに持っているコインを全て支払います。この時最大枚コインを持ってゴールするようにした際、その枚数を出力せよ。コインを無限枚に増やせる時は-1を出力せよ。

解法

この問題はABC061-DにScore Attackという類題が存在する。

kkt89.hatenablog.com

今回は追加の条件として、1秒経過後にPだけスコアが減少するので、辺のコストを-c+pとしてベルマンフォード法を適用すれば良い。

実装

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

template<typename T>
struct BellmanFord{
	struct Edge{
		int  from,to; ll cost;
		Edge(){}
		Edge(int from,int to,ll cost):from(from),to(to),cost(cost){}
	};

	int n;
	vector<vector<int> >G;
	vector<int> used,reach;
	BellmanFord(int n):n(n),G(n),used(n,0),reach(n,0){}

	vector<Edge> es;
	void add_edge(int from,int to,ll cost){
		es.push_back(Edge(from,to,cost));
		G[from].push_back(to);
	}

	void dfs(int v){
		if(used[v])return ;
		used[v]=1;
		for(int u:G[v]){
			dfs(u);
		}
	}
	ll build(int from,int to,int &neg_loop){
		for(int i=0;i<n;i++){
			fill(used.begin(),used.end(),0);
			dfs(i);
			reach[i]=used[to];
		}
		vector<ll> ds(n,1e18);
		ds[from]=0;
		for(int i=0;i<n;i++){
			bool update=0;
			for(auto e:es){
				if(!reach[e.from]||!reach[e.to]||ds[e.from]==1e18) continue;
				if(ds[e.to]>ds[e.from]+e.cost){
					ds[e.to]=ds[e.from]+e.cost;
					update=1;
				}
			}
			if(!update)break;
			if(i==n-1){
				neg_loop=1;
				return 1e18;
			}
		}
		neg_loop=0;
		return ds[to];
	}
};

int main(){
	int n,m,p; cin >> n >> m >> p;
	BellmanFord<int> G(n);
	for(int i=0;i<m;i++){
		int a,b,c; cin >> a >> b >> c;
		a--; b--;
		G.add_edge(a,b,p-c);
	}
	int neg_loop;
	int res=G.build(0,n-1,neg_loop);
	if(neg_loop){
		cout << -1 << endl;
		return 0;
	}
	else{
		cout << max((ll)0,(ll)-res) << endl;
		return 0;
	}
}

 感想

コンテスト終了後に嘘解法の話で持ちきりになっていた、上のコードは嘘で落ちなかった人のコードを参考にさせて頂いた