이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Jakarta skysrcapers
#include <bits/stdc++.h>
#define INF MOD
#define MOD 100000007
#define MAX_N 30005
#define MAX_M 30005
using namespace std;
int N, M;
int source, dest;
struct edge{
int d, w;
};
vector<int> soli[MAX_N];
vector<edge> adj[MAX_N];
int dist[MAX_N];
bool mark[MAX_N];
void dijkstra(int s){
memset(dist, INF, sizeof(dist));
memset(mark, 0, sizeof(mark));
dist[s]=0;
priority_queue<pair<int, int> > pq;
pq.emplace(0, s);
while(!pq.empty()){
auto cur=pq.top();
pq.pop();
int v=cur.second;
if(mark[v])continue;
//printf("v=%d\n", v);
mark[v]=1;
dist[v]=-1*cur.first;
int d=adj[v].size();
for(int i=0; i<d; ++i){
int u=adj[v][i].d;
if(!mark[u] && dist[u]>dist[v]+adj[v][i].w){
dist[u]=dist[v]+adj[v][i].w;
pq.emplace(-1*(dist[v]+adj[v][i].w), u);
}
}
}
}
int main(){
//ios::sync_with_stdio(false);
cin>>N>>M;
int b;
cin>>source>>b;
soli[source].push_back(b);
cin>>dest>>b;
soli[dest].push_back(b);
for(int i=2; i<M; ++i){
int p;
cin>>b>>p;
soli[b].push_back(p);
}
for(int i=0; i<N; ++i){
int d=soli[i].size();
for(int j=0; j<d; ++j){
int p=soli[i][j];
int sk=i-p;
while(sk>=0){
edge e;
e.d=sk;
e.w=(i-sk)/p;
adj[i].push_back(e);
sk-=p;
}
sk=i+p;
while(sk<N){
edge e;
e.d=sk;
e.w=(sk-i)/p;
adj[i].push_back(e);
sk+=p;
}
}
}
/*for(int i=0; i<N; ++i){
int d=adj[i].size();
printf("adj[%d]:", i);
for(int j=0; j<d; ++j){
printf("%d ", adj[i][j].d);
}
printf("\n");
}*/
dijkstra(source);
cout<<dist[dest];
return 0;
}
/*
5 3
0 2
1 1
4 1
*/
# | 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... |