結果

問題 No.1308 ジャンプビーコン
ユーザー yurujirou
提出日時 2021-10-17 19:03:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 465 ms / 4,000 ms
コード長 2,130 bytes
コンパイル時間 4,737 ms
コンパイル使用メモリ 258,256 KB
最終ジャッジ日時 2025-01-25 01:46:48
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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