| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 415011 | MeGustaElArroz23 | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cassert>
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
ll find_shortcut(int n, vi l, vi d, int c)
{
vvii conexiones(2*n);
for (int i=0;i<n-1;i++){
conexiones[i].push_back(pii{l[i],i+1});
conexiones[i+1].push_back(pii{l[i],i});
}
for (int i=0;i<n;i++){
conexiones[i].push_back(pii{d[i],i+n});
conexiones[n+i].push_back(pii{d[i],i});
}
ll mejor=INF;
for (int i=0;i<n;i++){
for (int j=i+1;j<n;j++){
vvii conex=conexiones;
conex[i].push_back(pii{c,j});
conex[j].push_back(pii){c,i};
ll mej=0;
for (int v=n;v<2*n;v++){
vector<bool> porvisitar(2*n,true);
priority_queue<pii> cola;
cola.push(pii{0,v});
while (cola.size()){
pii x=cola.front();
cola.pop();
if (porvisitar[x.second]){
mej=min(mej,-x.first);
for (pii y:conex[x]){
cola.push(pii{x.first-y.first,y.second});
}
}
}
}
mejor=min(mejor,mej);
}
}
return mejor;
}