結果

問題 No.1308 ジャンプビーコン
ユーザー 👑 NachiaNachia
提出日時 2020-12-06 14:12:48
言語 cLay
(20240714-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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 12 ms
6,144 KB
testcase_14 AC 12 ms
5,888 KB
testcase_15 AC 13 ms
6,016 KB
testcase_16 AC 13 ms
6,144 KB
testcase_17 AC 12 ms
5,888 KB
testcase_18 AC 558 ms
226,560 KB
testcase_19 AC 570 ms
226,560 KB
testcase_20 AC 564 ms
226,560 KB
testcase_21 AC 569 ms
226,688 KB
testcase_22 AC 563 ms
226,816 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 422 ms
226,560 KB
testcase_27 AC 408 ms
226,688 KB
testcase_28 AC 409 ms
226,560 KB
testcase_29 AC 420 ms
226,816 KB
testcase_30 AC 423 ms
226,688 KB
testcase_31 AC 346 ms
226,800 KB
testcase_32 AC 490 ms
226,560 KB
testcase_33 AC 540 ms
226,560 KB
testcase_34 AC 412 ms
226,560 KB
testcase_35 AC 416 ms
226,560 KB
testcase_36 AC 431 ms
226,560 KB
testcase_37 AC 425 ms
226,688 KB
testcase_38 AC 655 ms
226,560 KB
testcase_39 AC 668 ms
226,688 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