| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 89993 | thebes | Ferries (NOI13_ferries) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+5;
int i, x, y, dist[MN], idx[MN];
vector<int> adj[MN], w[MN];
typedef pair<int,int> pii;
struct pq{bool operator()(const pii&i,const pii&j){return i.second>j.second;}};
priority_queue<pii,vector<pii>,pq> q;
int ferries(int N,int M,int *A,int *B,int *C){
for(i=0;i<M;i++){
adj[B[i]].push_back(A[i]);
w[A[i]].push_back(C[i]);
}
for(i=1;i<=N;i++) sort(w[i].begin(),w[i].end(),[](int i,int j){return i>j;});
memset(dist,-1,sizeof(dist));
q.push({N,0});
while(q.size()){
auto v=q.top(); q.pop();
if(dist[v.first]!=-1) continue;
else dist[v.first]=v.second;
for(auto e : adj[v.first]){
if(dist[e]==-1){
int W = w[e][idx[e]]; idx[e]++;
q.push({e, W+v.second});
}
}
}
return dist[1];
}