| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 465269 | MohamedFaresNebili | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
int n, m, k; vector<pair<int, long long>>adj[100000];
vector<int>ex; vector<bool>e; long long d[1024][1024];
long long dfs(int v, int p)
{
if(e[v]) return 0;
long long best=1e9, ans=1e9; int node=-1;
for(auto u:adj[v]) {
int to=u.first; long long w=u.second;
if(to==p) continue;
long long cnt=1e9;
for(int l=0;l<k;l++) cnt=min(cnt, d[l][to]);
if(cnt+w<best) node=to, best=cnt+w;
}
for(auto u:adj[v]) {
int to=u.first; long long w=u.second;
if(to==p||to==node) continue;
ans=min(ans, w+dfs(to, v));
}
return ans;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n=N, m=M, k=K; e.assign(n, false);
for(int l=0;l<m;l++) {
int a=R[l][0], b=R[l][1]; long long w=L[l];
adj[a].push_back({b, w}); adj[b].push_back({a, w});
}
for(int l=0;l<k;l++) {
int i=P[l]; e[i]=true; ex.push_back(i);
}
int cnt=0;
for(auto u:ex) {
for(int i=0;i<n;i++) d[cnt][i]=1e9; d[cnt][u]=0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>pq;
pq.push({0, u}); vector<bool>vis(n);
while(!pq.empty()) {
int a=pq.top().second; pq.pop();
for(auto u:adj[a]) {
if(d[cnt][u.first]>d[cnt][a]+u.second) {
d[cnt][u.first]=d[cnt][a]+u.second;
pq.push({d[cnt][u.first], u.first});
}
}
}
cnt++;
}
N=dfs(0, -1);
return N;
}