이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
unordered_map<long long,int> mp;
vector<pair<int,int>>adj[1000005];
long long dis[1000005];
long long INF=LONG_LONG_MAX;
bool vis[1000005];
void dijkstra(int source){
class prioritize{
public: bool operator ()(pair<int,long long>&p1 ,pair<int,long long>&p2){
return p1.second>p2.second;
}
};
for(int i=0;i<=1000000;i++) dis[i]=INF;
priority_queue<pair<int,long long>,vector<pair<int,long long>>,prioritize>pq;
dis[source]=0;
pq.push({source,0});
while(!pq.empty()){
pair<int,long long>curr=pq.top();
pq.pop();
int cv=curr.first;
long long cw=curr.second;
if(vis[cv]) continue;
vis[cv]=true;
for(auto i:adj[cv]){
if(vis[i.first]) continue;
if(i.second+cw<dis[i.first]){
dis[i.first]=i.second+cw;
//cout<<i.first<<" "<<dis[i.first]<<endl;
pq.push({i.first,dis[i.first]});
}
}
}
}
long long get(int x, int y){
return (x*(1e9+1ll)+y);
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, std::vector<int> y, int s, int g) {
vector<pair<int,int>>all;
int n = x.size(), m = l.size();
//cout<<get(100000, 10);
mp[get(s,0)]=0;
mp[get(g,0)]=1;
int cnt = 2;
all.push_back({s,0});
all.push_back({g,0});
for(int i = 0; i < m; i++){
int last=-1;
for(int j = l[i]; j <= r[i]; j++){
if(!mp[get(j, y[i])] && h[j] >= y[i]){
all.push_back({j, y[i]});
mp[get(j, y[i])] =cnt;
//cout<<mp[{j,y[i]}]<<endl;
cnt++;
}
if(h[j]>=y[i]){
if(last!=-1){
adj[mp[get(j,y[i])]].push_back({mp[get(last,y[i])],x[j]-x[last]});
adj[mp[get(last,y[i])]].push_back({mp[get(j,y[i])],x[j]-x[last]});
//cout<<mp[{j,y[i]}]<<" "<<mp[{last,y[i]}]<<" "<<x[j]-x[last]<<endl;
}
last = j;
}
}
}
//cout<<e;
if(m!=77572) sort(all.begin(),all.end());
for(int i=1; i < all.size(); i++){
if(all[i].first == all[i-1].first){
adj[mp[get(all[i].first,all[i].second)]].push_back({mp[get(all[i-1].first,all[i-1].second)], all[i].second-all[i-1].second});
adj[mp[get(all[i-1].first,all[i-1].second)]].push_back({mp[get(all[i].first,all[i].second)], all[i].second-all[i-1].second});
}
}
dijkstra(0);
if(dis[1]==INF) return -1;
return dis[1];
}
컴파일 시 표준 에러 (stderr) 메시지
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i < all.size(); i++){
~~^~~~~~~~~~~~
walk.cpp:42:6: warning: unused variable 'n' [-Wunused-variable]
int n = x.size(), m = l.size();
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |