| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 140661 | eohomegrownapps | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e18;
vector<vector<pair<ll,ll> > > adjlist;
vector<ll> safe;
vector<ll> shortest;
vector<ll> secshortest;
ll n;
void dijkstra(){
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
for (ll i : safe){
pq.push(make_pair(0,i));
}
while (pq.size()>0){
auto f = pq.top();
pq.pop();
if (f.first>secshortest[f.second]){
continue;
}
//cout<<"process "<<f.second<<endl;
for (auto i : adjlist[f.second]){
if (secshortest[i.second]>secshortest[f.second]+i.first){
if (secshortest[f.second]+i.first<=shortest[i.second]){
secshortest[i.second]=shortest[i.second];
shortest[i.second]=secshortest[f.second]+i.first;
} else {
secshortest[i.second]=secshortest[f.second]+i.first;
}
pq.push(make_pair(secshortest[i.second],i.second));
}
}
/*for (ll i : shortest){
cout<<(i==INF?-1:i)<<" ";
}cout<<endl;
for (ll i : secshortest){
cout<<(i==INF?-1:i)<<" ";
}cout<<endl;
cout<<"==="<<endl;*/
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n=N;
adjlist.resize(n);
safe.resize(K);
shortest.resize(n,INF);
secshortest.resize(n,INF);
for (int i = 0; i<M; i++){
adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
}
for (int i = 0; i<K; i++){
safe[i]=P[i];
shortest[P[i]]=0;
secshortest[P[i]]=0;
}
dijkstra();
return secshortest[0];
}
#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 50000
#define MAX_M 10000000
static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&K));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
for(i=0; i<K; i++)
my_assert(1==scanf("%d",&P[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = travel_plan(N,M,R,L,K,P);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}