Submission #100790

#	Time	Username	Problem	Language	Result	Execution time	Memory
100790		JPN20	Wild Boar (JOI18_wild_boar)	C++17	47 / 100	18090 ms	315384 KiB

wild_boar

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

const long long INF = (1LL << 60);
long long N, M, T, L, X[100009], A[4009], B[4009], C[4009], dist[4009][4009];
long long prev_[1009], dp[1009]; vector<int> G[4009];
vector<pair<long long, int>> E[2009][4009];

int anti(int pos) {
	if (pos < M) return pos + M;
	return pos - M;
}

long long solve() {
	for (int i = 0; i < 2 * M; i++) { prev_[i] = INF; dp[i] = INF; }
	
	for (int i = 0; i < 2 * M; i++) {
		if (B[i] == X[1]) prev_[i] = 0;
	}
	
	for (int i = 2; i <= L; i++) {
		// 前半パート
		vector<pair<long long, int>> F;
		for (int j = 0; j < 2 * M; j++) {
			if (prev_[j] < INF) F.push_back(make_pair(prev_[j], j));
		}
		sort(F.begin(), F.end());
		
		// 後半パート
		for (int j = 0; j < (int)G[X[i]].size(); j++) {
			int pos = anti(G[X[i]][j]), B = min(2, (int)F.size());
			for (int k = 0; k < (int)E[X[i - 1]][pos].size(); k++) {
				for (int l = 0; l < B; l++) {
					if (abs(F[l].second - E[X[i - 1]][pos][k].second) == M && i >= 3) continue;
					dp[pos] = min(dp[pos], F[l].first + E[X[i - 1]][pos][k].first);
				}
			}
		}
		for (int j = 0; j < 2 * M; j++) { prev_[j] = dp[j]; dp[j] = INF; }
	}
	
	long long ans = (1LL << 60);
	for (int i = 0; i < 2 * M; i++) ans = min(ans, prev_[i]);
	return ans;
}

int main() {
	// 入力
	cin >> N >> M >> T >> L;
	for (int i = 0; i < M; i++) cin >> A[i] >> B[i] >> C[i];
	for (int i = 0; i < M; i++) { A[i + M] = B[i]; B[i + M] = A[i]; C[i + M] = C[i]; }
	for (int i = 0; i < 2 * M; i++) G[A[i]].push_back(i);
	
	// ワーシャルフロイドで距離を求める
	for (int i = 0; i < 2 * M; i++) {
		for (int j = 0; j < 2 * M; j++) {
			if (i == j) dist[i][j] = 0;
			else if (B[i] == A[j] && A[i] != B[j]) dist[i][j] = C[j];
			else dist[i][j] = INF;
		}
	}
	for (int k = 0; k < 2 * M; k++) {
		for (int i = 0; i < 2 * M; i++) {
			for (int j = 0; j < 2 * M; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
	for (int i = 0; i < 2 * M; i++) {
		for (int j = 0; j < 2 * M; j++) { if (dist[i][j] < INF) dist[i][j] += C[i]; }
	}
	
	// 各頂点から各辺に行くコストを求める
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 2 * M; j++) {
			for (int k = 0; k < (int)G[i].size(); k++) {
				E[i][j].push_back(make_pair(dist[G[i][k]][j], G[i][k]));
			}
			sort(E[i][j].begin(), E[i][j].end());
			while (E[i][j].size() >= 3) E[i][j].pop_back();
		}
	}
	
	// ここからが本質
	for (int i = 1; i <= L; i++) cin >> X[i];
	for (int i = 1; i <= T; i++) {
		int p, q; cin >> p >> q; X[p] = q;
		long long P = solve();
		if (P == INF) P = -1;
		cout << P << endl;
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38