제출 #553259

#제출 시각아이디문제언어결과실행 시간메모리
553259ala2Jakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
19 ms23892 KiB
#include <bits/stdc++.h> #define int long long #define F first #define S second #define pb push_back #define B begin() #define E end() using namespace std; int a[1001000]; int b[1001000]; vector<pair<int,int>>v[1001000]; int dist(int i,int j) { return abs(a[j]-a[i]); } int dis[1001000]; const int inf=1e17; signed main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { cin>>a[i]>>b[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=m;j++) { if(j==i) continue; if( dist(i,j)%b[i]==0 ){ // cout<<" "<<i<<" "<<j<<endl; v[i].pb({j,dist(i,j)/b[i]}); } } } for(int i=2;i<=m;i++) { dis[i]=inf; } priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; q.push({0,1}); while(!q.empty()) { // cout<<"D"; pair<int,int>x=q.top(); q.pop(); // cout<<" :::: "<<x.S<<endl; for(auto i:v[x.S]) { int ned=x.F+i.S; // cout<<" "<<i.F<<" "<<ned<<endl; if(ned<dis[i.F]) { dis[i.F]=ned; q.push({ned,i.F}); } } } cout<<dis[2]<<endl; }
#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...