結果

問題 No.1308 ジャンプビーコン
ユーザー 👑 NachiaNachia
提出日時 2020-12-06 14:12:48
言語 cLay
(20240104-1)
結果
AC  
実行時間 630 ms / 4,000 ms
コード長 713 bytes
コンパイル時間 2,236 ms
コンパイル使用メモリ 170,936 KB
実行使用メモリ 227,228 KB
最終ジャッジ日時 2023-09-19 01:55:06
合計ジャッジ時間 13,071 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,636 KB
testcase_01 AC 3 ms
7,504 KB
testcase_02 AC 2 ms
7,492 KB
testcase_03 AC 3 ms
7,512 KB
testcase_04 AC 3 ms
7,504 KB
testcase_05 AC 3 ms
7,800 KB
testcase_06 AC 3 ms
7,504 KB
testcase_07 AC 3 ms
7,584 KB
testcase_08 AC 3 ms
7,612 KB
testcase_09 AC 3 ms
7,596 KB
testcase_10 AC 3 ms
7,816 KB
testcase_11 AC 3 ms
7,752 KB
testcase_12 AC 3 ms
7,572 KB
testcase_13 AC 11 ms
16,268 KB
testcase_14 AC 14 ms
16,336 KB
testcase_15 AC 13 ms
16,344 KB
testcase_16 AC 13 ms
16,296 KB
testcase_17 AC 12 ms
16,476 KB
testcase_18 AC 532 ms
226,992 KB
testcase_19 AC 531 ms
227,140 KB
testcase_20 AC 532 ms
226,948 KB
testcase_21 AC 532 ms
227,000 KB
testcase_22 AC 529 ms
227,004 KB
testcase_23 AC 2 ms
7,648 KB
testcase_24 AC 3 ms
7,516 KB
testcase_25 AC 3 ms
7,680 KB
testcase_26 AC 443 ms
226,916 KB
testcase_27 AC 422 ms
227,056 KB
testcase_28 AC 420 ms
226,860 KB
testcase_29 AC 420 ms
227,228 KB
testcase_30 AC 424 ms
227,004 KB
testcase_31 AC 347 ms
227,080 KB
testcase_32 AC 486 ms
226,948 KB
testcase_33 AC 539 ms
226,976 KB
testcase_34 AC 421 ms
226,940 KB
testcase_35 AC 423 ms
226,808 KB
testcase_36 AC 432 ms
227,112 KB
testcase_37 AC 433 ms
226,956 KB
testcase_38 AC 621 ms
226,900 KB
testcase_39 AC 630 ms
226,980 KB
権限があれば一括ダウンロードができます

ソースコード

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