Submission #1233453

#TimeUsernameProblemLanguageResultExecution timeMemory
1233453dssfsuper2자매 도시 (APIO20_swap)C++20
0 / 100
0 ms324 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; vector<vector<pii>> adj; multiset<pii> stac; vector<pii> lowest; int n,m; void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) { n=N; m=M; adj.resize(N+1); for(int i = 0;i<M;i++){ adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } } int dijkstra(int X, int Y){ stac.clear(); stac.insert({0, X}); lowest.assign(n+1, {1e9+1, 1e9+1}); lowest[X]={0, 1e9+1}; while(!stac.empty()){ auto node = *(stac.begin()); stac.erase(stac.begin()); if(lowest[node.second].second!=1e9+1 )continue; if(node.first>=lowest[node.second].first)lowest[node.second].second=node.first; else lowest[node.second].first=node.first; for(auto thing:adj[node.second]){ if(lowest[thing.first].second<=max(thing.second, node.first))continue; stac.insert({max(node.first, thing.second), thing.first}); } } return lowest[Y].second; } int getMinimumFuelCapacity(int X, int Y) { return dijkstra(X, Y); }
#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...