제출 #1040243

#제출 시각아이디문제언어결과실행 시간메모리
1040243dpsaveslivesJakarta Skyscrapers (APIO15_skyscraper)C++17
10 / 100
1077 ms484 KiB
#include <bits/stdc++.h> #define f first #define s second #define ll long long using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N,M; cin >> N >> M; vector<pair<int,int>> doges(M); for(int i = 0;i<M;++i){ cin >> doges[i].f >> doges[i].s; } priority_queue<pair<ll,int>> pq; pq.push({0,1}); vector<ll> dist(M,-1); dist[1] = 0; while(!pq.empty()){ int j = pq.top().s, cd = pq.top().f; pq.pop(); if(dist[j] != cd) continue; for(int i = 0;i<M;++i){ if(i == j) continue; if(doges[i].f == doges[j].f){ if(cd < dist[i] || dist[i] == -1){ dist[i] = cd; pq.push({dist[i],i}); } continue; } if((abs(doges[j].f-doges[i].f)) % doges[i].s == 0){ ll x = abs(doges[j].f-doges[i].f)/doges[i].s; if(x+cd < dist[i] || dist[i] == -1){ dist[i] = x+cd; pq.push({dist[i],i}); } } } } cout << dist[0] << "\n"; return 0; }
#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...