| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 726182 | GusterGoose27 | Wild Boar (JOI18_wild_boar) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, bool> plb;
typedef pair<ll, int> pli;
const int MAXN = 500;
const int MAX_PATH = 1e5;
const ll inf = 1e15;
int n, m, t, l;
class path {
public:
ll len;
int s, e;
path(ll l, int s, int e) : len(l), s(s), e(e) {}
path() {}
};
int hsh(int i, int j) {
return n*i+j; // j is prev node, i is cur node
}
vector<pii> edges[MAXN];
vector<pii> edges2[MAXN*MAXN];
ll dist[MAXN*MAXN][MAXN*MAXN];
int seq[MAX_PATH];
void dijkstra(int s) {
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dist[s], dist[s]+n*n, inf);
dist[s][s] = 0;
pq.push(pli(0, s));
while (!pq.empty()) {
pii tp = pq.top();
pq.pop();
if (dist[s][tp.second] < tp.first) continue;
for (pii e: edges2[tp.second]) {
ll ndist = tp.first+e.second;
if (ndist < dist[s][e.first]) {
dist[s][e.first] = ndist;
pq.push(pli(ndist, e.first));
}
}
}
}
ll dp[MAX_PATH][MAXN];
ll make_dp() {
fill(dp[l-1], dp[l-1]+n, 0);
for (int i = l-2; i > 0; i--) {
for (pii j: edges[seq[i]]) {
dp[i][j.first] = inf;
for (pii k: edges[seq[i+1]]) {
dp[i][j.first] = min(dp[i][j.first], dp[i+1][k.first]+dist[hsh(seq[i],j.first)][hsh(seq[i+1], k.first)]);
}
}
}
ll ans = inf;
for (pii i: edges[seq[0]])
for (pii j: edges[seq[1]]) ans = min(ans, dp[1][j.first]+i.second+dist[hsh(i.first, seq[0])][hsh(seq[1], j.first)]);
if (ans == inf) return -1;
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m >> t >> l;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c; a--; b--;
edges[a].push_back(pii(b, c));
edges[b].push_back(pii(a, c));
}
for (int i = 0; i < n; i++) {
for (pii j: edges[i]) {
for (pii k: edges[i]) {
if (k.first == j.first) continue;
edges2[hsh(i, j.first)].push_back(pii(hsh(k.first, i), k.second));
}
}
}
for (int i = 0; i < n*n; i++) {
dijkstra(i);
}
for (int i = 0; i < l; i++) {
cin >> seq[i]; seq[i]--;
}
for (int i = 0; i < t; i++) {
int p, v; cin >> p >> v;
p--; v--;
seq[p] = v;
cout << make_dp() << "\n";
}
}