#include <bits/stdc++.h>
using namespace std;
const long long INF = 99;
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;
cout << solve() << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
189688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
189688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
189688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
189688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
