結果

問題 No.1308 ジャンプビーコン
コンテスト
ユーザー Nachia
提出日時 2020-12-06 14:12:48
言語 cLay
(20241019-1)
結果
AC  
実行時間 668 ms / 4,000 ms
コード長 713 bytes
コンパイル時間 2,531 ms
コンパイル使用メモリ 182,672 KB
実行使用メモリ 226,816 KB
最終ジャッジ日時 2024-07-05 14:49:30
合計ジャッジ時間 12,907 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

const ll INF=1d18,Z=3001;

struct Edge{ ll to,d; };

ll N,Q,C;
vector<Edge>E[Z];
ll X[Z],D[Z][Z],P[Z][Z],T[Z],B[Z];
vector<ll> I[Z];

{
	rd(N,Q,C);
	rep(i,N-1){
		ll u,v,d; rd(u--,v--,d);
		E[u].push_back({v,d});
		E[v].push_back({u,d});
	}
	rd(X(Q)--);
	D[0..N][0...N]=P[0..N][0...N]=-1;
	rep(s,N){
		auto& Q=I[s];
		D[s][s]=0; Q.push_back(s);
		rep(i,Q.size()){
			ll p=Q[i];
			for(Edge e:E[p]) if(D[s][e.to]==-1){
				D[s][e.to]=D[s][p]+e.d;
				P[s][e.to]=p;
				Q.push_back(e.to);
			}
		}
	}
	T[0..N]=INF; T[X[0]]=0;
	rep(i,Q-1){
		ll s=X[i],t=X[i+1];
		B[0..N]=T[0..N]+C; B[s]=T[s];
		for(ll p:I[s]) for(Edge e:E[p]) B[e.to]<?=B[p]+e.d;
		rep(j,N) T[j]=min(B[j]+D[j][t],T[j]+D[s][t]);
	}
	wt(T[X[Q-1]]);
}
0