Submission #1178249

#TimeUsernameProblemLanguageResultExecution timeMemory
1178249InvMODCrocodile's Underground City (IOI11_crocodile)C++20
100 / 100
276 ms46820 KiB
#include<bits/stdc++.h> using namespace std; //#define name "InvMOD" #ifndef name #include "crocodile.h" #endif // name #define sz(v) (int)(v).size() int travel_plan(int n, int m, int R[][2], int L[], int K, int P[]){ vector<vector<pair<int,int>>> adj(n, vector<pair<int,int>>()); for(int i = 0; i < m; i++){ int u = R[i][0], v = R[i][1]; adj[u].emplace_back(v, L[i]); adj[v].emplace_back(u, L[i]); } const int inf = 1e9; vector<vector<int>> dist(n, vector<int>(2, inf)); for(int i = 0; i < K; i++){ int x = P[i]; dist[x][0] = 0; dist[x][1] = 0; } priority_queue<pair<int, int>> pq; for(int i = 0; i < K; i++) pq.push({0, P[i]}); while(!pq.empty()){ pair<int,int> eq = pq.top(); pq.pop(); int cur_dist = -eq.first, x = eq.second; if(cur_dist == inf || cur_dist > dist[x][1]) continue; for(pair<int,int> e : adj[x]){ int v = e.first, w = e.second; if(cur_dist + w < dist[v][0]){ if(dist[v][0] < dist[v][1]) pq.push({-dist[v][0], v}); dist[v][1] = dist[v][0]; dist[v][0] = cur_dist + w; } else if(cur_dist + w < dist[v][1]){ dist[v][1] = cur_dist + w; pq.push({-dist[v][1], v}); } } } return dist[0][1]; } #ifdef name int32_t main(){ freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout); int n,m,k; cin >> n >> m >> k; int E[m][2], L[m], P[k]; for(int i = 0; i < m; i++){ cin >> E[i][0] >> E[i][1] >> L[i]; } for(int i = 0; i < k; i++){ cin >> P[i]; } cout << travel_plan(n, m, E, L, k, P) << "\n"; return 0; } #endif // name
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...