| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 367605 | Iwanttobreakfree | Crocodile's Underground City (IOI11_crocodile) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "crocodile.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long int travel_plan(long long int N, long long int M, long long int R[][2], long long int L[],long long int K,long long int P[]){
vector<long long int> distancia(N,1e9);
long long int maximo=0;
vector<vector<pair<long long int,long long int> > > conexiones(N,vector<pair<long long int,long long int> >());
for(long long int i=0;i<M;i++){
conexiones[R[i][0]].push_back(make_pair(L[i],R[i][1]));
conexiones[R[i][1]].push_back(make_pair(L[i],R[i][0]));
}
priority_queue <pair<long long int,long long int> > q;
q.push(make_pair(0,0));
distancia[0]=0;
long long int nodo,coste;
while(!q.empty()){
nodo=q.top().second;
coste=-q.top().first;
q.pop();
if(coste>distancia[nodo])continue;
for(pair<long long int,long long int> con:conexiones[nodo]){
long long int arista=-con.first;
long long int siguiente=con.second;
if(distancia[siguiente]>distancia[nodo]+arista){
distancia[siguiente]=distancia[nodo]+arista;
q.push(make_pair(-arista,siguiente));
}
}
}
for(long long int i=0;i<K;i++){
maximo=max(maximo,distancia[P[i]]);
}
return maximo;
}