| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 279968 | shinjan | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
#define maxN 100001
#define maxM 1000001
#include "crocodile.h"
using namespace std;
vector<pair<int,int>> drvo[maxN];
bitset <maxN> spec;
int mini[maxN];
int siguran[maxN];
void namesti(int n)
{
for(int i=0;i<n;i++)
{
siguran[i]=-1;
mini[i]=-1;
}
}
void dfs(int v,int par)
{
int cvor,w;
for(pair<int,int> p:drvo[v])
{
cvor=p.first;
w=p.second;
if(cvor!=par)
{
if(spec[cvor])
{
if(mini[v]>=w || mini[v]==-1)
{
siguran[v]=mini[v];
mini[v]=w;
}
else if(w<siguran[v] || siguran[v]==-1)
{
siguran[v]=w;
}
}
else{
dfs(cvor,v);
if(siguran[cvor]!=-1 && (siguran[cvor]+w<=mini[v] || mini[v]==-1))
{
siguran[v]=mini[v];
mini[v]=siguran[cvor]+w;
}
else if(siguran[cvor]!=-1 && (siguran[cvor]+w<siguran[v] || siguran[v]==-1))
{
siguran[v]=siguran[cvor]+w;
}
}
}
}
}
int travel_plan(int n,int m,int r[maxM][2],int l[maxM],int k,int p[maxN])
{
for(int i=0;i<m;i++)
{
drvo[r[i][0]].push_back({r[i][1],l[i]});
drvo[r[i][1]].push_back({r[i][0],l[i]});
}
for(int i=0;i<k;i++)
{
spec[p[i]]=1;
if(p[i]==0)
return 0;
}
dfs(0,-1);
return siguran[0];
}