#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)
const int MAX_N = 19;
const int MAX_CANDIDATE = 2;
const int MAX_PREV = 4;
int N, M, L, T, A[MAX_N], B[MAX_N], C[MAX_N], P[100009];
vector<pair<int, long long>> G[MAX_N];
tuple<long long, int, int> dist[MAX_N][MAX_N][MAX_CANDIDATE * MAX_PREV];
pair<long long, int> dp[100009][2];
int cnt1[MAX_N][MAX_N], cnt2[MAX_N], cnt3[MAX_N];
tuple<long long, int, int> R[19]; int sz;
void hosei() {
int dt = 0, kinds = 0;
for (int i = 0; i < sz; i++) {
int v1 = get<1>(R[i]), v2 = get<2>(R[i]);
if (cnt1[v1][v2] >= 1) continue;
if (cnt2[v1] >= MAX_PREV) continue;
if (cnt3[v2] >= MAX_CANDIDATE) continue;
if (cnt3[v2] == 0) {
if (kinds >= MAX_CANDIDATE) continue;
kinds++;
}
R[dt] = R[i]; dt++;
cnt1[v1][v2]++; cnt2[v1]++; cnt3[v2]++;
}
for (int i = 0; i < dt; i++) {
int v1 = get<1>(R[i]), v2 = get<2>(R[i]);
cnt1[v1][v2] = 0; cnt2[v1] = 0; cnt3[v2] = 0;
}
sz = dt;
}
void init(int pos) {
for (int i = 1; i <= N; i++) {
for (int j = 0; j < MAX_CANDIDATE * MAX_PREV; j++) dist[pos][i][j] = make_tuple(1LL << 60, -1, -1);
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>Q;
dist[pos][pos][0] = make_tuple(0, -1, -1);
for (int i = 0; i < G[pos].size(); i++) {
int to = G[pos][i].first; long long cost = G[pos][i].second;
dist[pos][to][0] = make_tuple(cost, to, pos);
Q.push(make_pair(cost, to));
}
// 各 dist に対する上位 6 点を記録する
while (!Q.empty()) {
int cur = Q.top().second; Q.pop();
for (int i = 0; i < G[cur].size(); i++) {
int to = G[cur][i].first; long long cost = G[cur][i].second;
sz = 0;
for (int j = 0; j < MAX_CANDIDATE * MAX_PREV; j++) {
if (get<0>(dist[pos][to][j]) != (1LL << 60)) { R[sz] = dist[pos][to][j]; sz++; }
}
for (int j = 0; j < MAX_CANDIDATE * MAX_PREV; j++) {
if (get<2>(dist[pos][cur][j]) == to) continue;
long long val = get<0>(dist[pos][cur][j]) + cost;
long long v1 = get<1>(dist[pos][cur][j]);
long long v2 = cur; if (v1 == -1) v1 = to;
if (val < (1LL << 60)) { R[sz] = make_tuple(val, v1, v2); sz++; }
}
sort(R, R + sz); hosei();
long long flag = (1LL << 60);
for (int j = 0; j < min(sz, MAX_CANDIDATE * MAX_PREV); j++) {
if (dist[pos][to][j] > R[j]) {
flag = min(flag, get<0>(R[j]));
flag = true;
dist[pos][to][j] = R[j];
}
}
if (flag < (1LL << 60)) {
Q.push(make_pair(flag, to));
}
}
}
}
long long solve() {
for (int i = 1; i <= L; i++) {
dp[i][0] = make_pair(1LL << 60, -1);
dp[i][1] = make_pair(1LL << 60, -1);
}
for (int i = 0; i < min(2, (int)G[P[1]].size()); i++) {
dp[1][i] = make_pair(0LL, G[P[1]][i].first);
}
for (int t = 2; t <= L; t++) {
vector<pair<long long, int>> vec;
int from = P[t - 1], to = P[t];
for (int j = 0; j < 2; j++) {
if (dp[t - 1][j].first == (1LL << 60)) continue;
for (int k = 0; k < MAX_CANDIDATE * MAX_PREV; k++) {
if ((t >= 3 && dp[t - 1][j].second == get<1>(dist[from][to][k])) || get<0>(dist[from][to][k]) == (1LL << 60)) continue;
vec.push_back(make_pair(dp[t - 1][j].first + get<0>(dist[from][to][k]), get<2>(dist[from][to][k])));
}
}
sort(vec.begin(), vec.end());
for (int j = 0; j < vec.size(); j++) {
if (j == 0) dp[t][0] = vec[j];
else if (vec[j].second != vec[j - 1].second) {
dp[t][1] = vec[j]; break;
}
}
}
if (dp[L][0].first == (1LL << 60)) return -1LL;
return dp[L][0].first;
}
int main() {
scanf("%d%d%d%d", &N, &M, &T, &L);
for (int i = 1; i <= M; i++) {
scanf("%d%d%d", &A[i], &B[i], &C[i]);
G[A[i]].push_back(make_pair(B[i], C[i]));
G[B[i]].push_back(make_pair(A[i], C[i]));
}
for (int i = 1; i <= L; i++) scanf("%d", &P[i]);
for (int i = 1; i <= N; i++) init(i);
for (int i = 1; i <= T; i++) {
int v1, v2; scanf("%d%d", &v1, &v2);
P[v1] = v2;
printf("%lld\n", solve());
}
return 0;
}
Compilation message
wild_boar.cpp:9:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
wild_boar.cpp: In function 'void init(int)':
wild_boar.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
wild_boar.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[cur].size(); i++) {
~~^~~~~~~~~~~~~~~
wild_boar.cpp: In function 'long long int solve()':
wild_boar.cpp:115:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &N, &M, &T, &L);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:134:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= L; i++) scanf("%d", &P[i]);
~~~~~^~~~~~~~~~~~~
wild_boar.cpp:139:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int v1, v2; scanf("%d%d", &v1, &v2);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
