Submission #981073

#TimeUsernameProblemLanguageResultExecution timeMemory
981073AbitoSwapping Cities (APIO20_swap)C++17
0 / 100
2044 ms35148 KiB
#include "swap.h" #include <bits/stdc++.h> #define F first #define S second #define ep insert #define pb push_back using namespace std; const int NN=1e3+5; int n,m,dis[NN][NN]; vector<pair<int,int>> adj[NN]; bool vis[NN][NN]; void dijkstra(int X,int Y){ for (int i=0;i<n;i++) for (int j=0;j<n;j++) dis[i][j]=INT_MAX,vis[i][j]=0; dis[X][Y]=0; priority_queue<vector<int>> pq; pq.push({0,X,Y}); while (!pq.empty()){ int i=pq.top()[1],j=pq.top()[2]; pq.pop(); if (vis[i][j]) continue; vis[i][j]=1; for (auto u:adj[i]){ if (u.F==j) continue; int d=max(dis[i][j],u.S); if (d<dis[u.F][j]){ dis[u.F][j]=d; pq.push({-d,u.F,j}); } } for (auto u:adj[j]){ if (u.F==i) continue; int d=max(dis[i][j],u.S); if (d<dis[i][u.F]){ dis[i][u.F]=d; pq.push({-d,i,u.F}); } } }return; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n=N,m=M; for (int i=0;i<m;i++){ adj[U[i]].pb({V[i],W[i]}); adj[V[i]].pb({U[i],W[i]}); } return; } int getMinimumFuelCapacity(int X, int Y) { dijkstra(X,Y); /*for (int i=0;i<n;i++){ for (int j=0;j<n;j++){ cout<<dis[i][j]<<' '; }cout<<endl; }*/ if (dis[Y][X]==INT_MAX) return -1; return dis[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...