結果

問題 No.1308 ジャンプビーコン
ユーザー yurujirouyurujirou
提出日時 2021-10-17 19:03:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 401 ms / 4,000 ms
コード長 2,130 bytes
コンパイル時間 6,189 ms
コンパイル使用メモリ 268,580 KB
実行使用メモリ 145,384 KB
最終ジャッジ日時 2023-10-17 22:31:48
合計ジャッジ時間 10,298 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,820 KB
testcase_01 AC 2 ms
5,820 KB
testcase_02 AC 3 ms
5,840 KB
testcase_03 AC 3 ms
7,956 KB
testcase_04 AC 3 ms
7,956 KB
testcase_05 AC 3 ms
7,956 KB
testcase_06 AC 3 ms
7,956 KB
testcase_07 AC 3 ms
7,956 KB
testcase_08 AC 5 ms
18,204 KB
testcase_09 AC 5 ms
18,204 KB
testcase_10 AC 5 ms
18,204 KB
testcase_11 AC 5 ms
18,204 KB
testcase_12 AC 5 ms
18,204 KB
testcase_13 AC 23 ms
75,060 KB
testcase_14 AC 22 ms
73,488 KB
testcase_15 AC 23 ms
73,488 KB
testcase_16 AC 22 ms
73,492 KB
testcase_17 AC 22 ms
73,492 KB
testcase_18 AC 219 ms
145,280 KB
testcase_19 AC 217 ms
145,280 KB
testcase_20 AC 219 ms
145,280 KB
testcase_21 AC 218 ms
145,280 KB
testcase_22 AC 217 ms
145,280 KB
testcase_23 AC 2 ms
5,808 KB
testcase_24 AC 17 ms
75,556 KB
testcase_25 AC 17 ms
75,556 KB
testcase_26 AC 143 ms
145,276 KB
testcase_27 AC 143 ms
145,276 KB
testcase_28 AC 143 ms
145,276 KB
testcase_29 AC 284 ms
145,348 KB
testcase_30 AC 280 ms
145,348 KB
testcase_31 AC 401 ms
145,348 KB
testcase_32 AC 325 ms
145,384 KB
testcase_33 AC 386 ms
145,384 KB
testcase_34 AC 142 ms
145,276 KB
testcase_35 AC 143 ms
145,276 KB
testcase_36 AC 151 ms
145,292 KB
testcase_37 AC 151 ms
145,292 KB
testcase_38 AC 294 ms
145,284 KB
testcase_39 AC 302 ms
145,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define RREP(i,n) for(int i = (int)n-1; i >= 0; i--)
#define LREP(i,n) for(LL i = 0; i < (LL)n; i++)

#define Vi vector<int>
#define Vl vector<long long>
#define P pair<int, int>
#define LP pair<long long ,long long>
#define T3 tuple<LL, LL, LL>
#define T4 tuple<LL, LL, LL, LL>
#define INF 1000000007
#define SIZE 3010
#define MOD 998244353
typedef long long LL;

LL N, Q, C;
vector<LP> E[SIZE];
LL X[SIZE];
LL dist[SIZE][SIZE];
LL dp[SIZE][SIZE];

void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) dist[i][j] = -1;
		dist[i][i] = 0;
		queue<int> que;
		que.push(i);
		while (que.size()) {
			int u = que.front();
			que.pop();
			for (auto e : E[u]) {
				if (dist[i][e.first] == -1) {
					dist[i][e.first] = dist[i][u] + e.second;
					que.push(e.first);
				}
			}
		}
	}
}

int main() {
	cin >> N >> Q >> C;
	REP(i, N - 1) {
		LL u, v, l;
		cin >> u >> v >> l;
		E[u].push_back(LP(v, l));
		E[v].push_back(LP(u, l));
	}
	REP(i, Q) cin >> X[i + 1];
	init();

	REP(i, Q + 1) REP(j, N + 1) dp[i][j] = 1e18;
	for (int q = 1; q < Q; q++) {
		Vl A, B;
		int t = X[q + 1], s = X[q];
		while (t != s) {
			for (auto e : E[t]) {
				if (dist[s][e.first] == dist[s][t] - e.second) {
					A.push_back(t);
					t = e.first;
					break;
				}
			}
		}
		A.push_back(s);
		t = X[q + 1];
		LL m = 1e18;
		for (int i = 1; i <= N; i++) {
			dp[q][i] = min(dp[q][i], dp[q - 1][i] + dist[s][t]);
			m = min(m, dp[q][i]);
		}
		REP(i, A.size()) {
			dp[q][A[i]] = min(dp[q][A[i]], m);
		}

		for (auto u : A) {
			B.push_back(C + dp[q - 1][u] + dist[u][t]);
		}
		reverse(A.begin(), A.end());
		reverse(B.begin(), B.end());
		REP(i, B.size() - 1) {
			if (B[i + 1] > B[i]) {
				B[i + 1] = B[i];
			}
		}
		REP(i, A.size()) {
			dp[q][A[i]] = min(dp[q][A[i]], B[i]);
			if (q == 1) dp[q][A[i]] = dist[s][t];
		}
	}
	LL ans = 1e18;
	for (int i = 1; i <= N; i++) ans = min(ans, dp[Q - 1][i]);
	cout << ans << endl;
}
0