結果

問題 No.1308 ジャンプビーコン
ユーザー yurujirouyurujirou
提出日時 2021-10-17 18:45:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,012 bytes
コンパイル時間 4,571 ms
コンパイル使用メモリ 270,008 KB
実行使用メモリ 145,384 KB
最終ジャッジ日時 2023-10-17 22:31:32
合計ジャッジ時間 10,566 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,820 KB
testcase_01 AC 2 ms
5,820 KB
testcase_02 AC 2 ms
5,840 KB
testcase_03 AC 3 ms
7,956 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 203 ms
145,280 KB
testcase_23 AC 2 ms
5,808 KB
testcase_24 AC 18 ms
75,556 KB
testcase_25 AC 17 ms
75,556 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 401 ms
145,348 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 138 ms
145,276 KB
testcase_35 AC 138 ms
145,276 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

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];
		for (int i = 1; i <= N; i++) {
			dp[q][i] = dp[q - 1][i] + dist[s][t];
		}

		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