| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 415013 | MeGustaElArroz23 | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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.top();
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;
}