Submission #288271

#TimeUsernameProblemLanguageResultExecution timeMemory
288271BlagojceWild Boar (JOI18_wild_boar)C++11
47 / 100
16918 ms1048580 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define pb push_back #define st first #define nd second #define pq priority_queue #define all(x) begin(x), end(x) #include <time.h> #include <cmath> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,ll> pii; const int i_inf = 1e9; const ll inf = 1e18; const ll mod = 1000000007; const ld eps = 1e-13; const ld pi = 3.14159265359; mt19937 _rand(time(NULL)); clock_t timer = clock(); const int mxn = 2e5+5; const ll A = 911382323; const ll B = 972663749; void solve(){ int n, m, t, len; cin >> n >> m >> t >> len; vector<pii> g[n]; int l[m+1], r[m+1]; fr(i, 0, m){ int u, v, w; cin >> u >> v >> w; --u, --v; l[i+1] = u, r[i+1] = v; g[u].pb({i+1, w}); g[v].pb({i+1, w}); } int a[len]; fr(i, 0, len){ cin >> a[i]; --a[i]; } fr(I, 0, t){ int p, q; cin >> p >> q; a[p-1] = q-1; l[0] = r[0] = a[0]; bool vis[2][m+1][len]; memset(vis, false, sizeof(vis)); ll dist[2][m+1][len]; fr(i, 0, 2) fr(j, 0, m+1) fr(k, 0, len) dist[i][j][k] = inf; pq<pair<ll, pair<int,pii> > > Q; Q.push({0, {0, {0, 0}}}); dist[0][0][0] = 0; while(!Q.empty()){ int side = Q.top().nd.st; int edge = Q.top().nd.nd.st; int k = Q.top().nd.nd.nd; Q.pop(); if(vis[side][edge][k]) continue; vis[side][edge][k] = true; int u; if(side == 0){ u = l[edge]; } else{ u = r[edge]; } for(auto e : g[u]){ if(e.st == edge) continue; int newside, newnode; if(u == l[e.st]){ newnode = r[e.st]; newside = 1; } else{ newnode = l[e.st]; newside = 0; } int newk = k; if(newnode == a[k+1]){ newk += 1; } if(dist[side][edge][k] + e.nd < dist[newside][e.st][newk]){ dist[newside][e.st][newk] = dist[side][edge][k] + e.nd; Q.push({-dist[newside][e.st][newk], {newside,{e.st, newk}}}); } } } ll ans = inf; for(auto u : g[a[len-1]]){ int side; if(a[len-1] == l[u.st]) side = 0; else side = 1; ans = min(ans, dist[side][u.st][len-1]); } if(ans == inf)cout<<-1<<endl; else cout<<ans<<endl; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int tc = 1; //cin >> tc; while(tc--) solve(); } /* 5 10 1 10 1 2 8 1 3 5 1 4 2 1 5 1 2 3 7 2 4 9 2 5 6 3 4 10 3 5 10 4 5 6 4 2 4 3 5 3 1 4 3 5 3 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...