Submission #1190488

#TimeUsernameProblemLanguageResultExecution timeMemory
1190488zh_hSwapping Cities (APIO20_swap)C++17
0 / 100
0 ms324 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; vector<vector<pair<int, int>>> edge; vector<vector<int>> cost; int N; void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) { edge.resize(n+1); for (int i = 0; i < m; i ++) { edge[u[i]].pb({v[i], w[i]}); edge[v[i]].pb({u[i], w[i]}); } N = n; } int getMinimumFuelCapacity (int x, int y) { cost.clear(); cost.resize(N+1, vector<int>(N+1, 1e9)); priority_queue<pair<int, pair<int, int>>> q; vector<vector<int>> visited(N+1, vector<int>(N+1, false)); cost[x][y] = 0; visited[x][y] = true; q.push({0, {x, y}}); while (!q.empty()) { int w = -q.top().first; int a = q.top().second.first, b = q.top().second.second; q.pop(); visited[a][b] = true; cost[a][b] = w; for (auto i : edge[a]) { if (i.first == b) continue; if (visited[i.first][b]) continue; int new_w = max(w, i.second); q.push({-new_w, {i.first, b}}); } for (auto i : edge[b]) { if (i.first == a) continue; if (visited[a][i.first]) continue; int new_w = max(w, i.second); q.push({-new_w, {a, i.first}}); } } return cost[y][x];; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...