#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define int long long
const int inf=1e9;
int farthest(int a, vector<vector<pair<int,int> > >& adi, int n){
vector<int> dist(n, inf);
vector<bool> vis(n);
dist[a]=0;
priority_queue<pair<int,int> > pq;
pq.push({-0, a});
int ans=a;
while(!pq.empty()){
int v=pq.top().second;
pq.pop();
if(vis[v]) continue;
vis[v]=true;
ans=v;
for(auto u: adi[v]){
if(dist[v]+u.second<dist[u.first]){
dist[u.first]=dist[v]+u.second;
pq.push({-dist[u.first], u.first});
}
}
}
return dist[ans];
}
int diameter(int n, vector<vector<pair<int,int> > >& adi){
int ans=0;
for(int i=0; i<n; i++){
ans=max(ans, farthest(i, adi, n));
}
return ans;
}
long long find_shortcut(int32_t n, std::vector<int> l, std::vector<int> d, int32_t c)
{
vector<vector<pair<int,int> > > adi(n*2);
for(int i=0; i<n-1; i++){
adi[i].push_back({i+1, l[i]});
adi[i+1].push_back({i, l[i]});
}
for(int i=0; i<n; i++){
adi[i].push_back({i+n, d[i]});
adi[i+n].push_back({i, d[i]});
}
int best=diameter(n*2, adi);
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
adi[i].push_back({j, c});
adi[j].push_back({i, c});
/*if(diameter(n*2, adi)<best){
cout << "=> " << diameter(n*2, adi) << " " << i << " " << j << "\n";
}*/
best=min(best, diameter(n*2, adi));
adi[i].pop_back();
adi[j].pop_back();
}
}
return best;
}
/*signed main(){
int n;
cin >> n;
vector<int> l(n-1);
for(int i=0; i<n-1; i++){
cin >> l[i];
}
vector<int> d(n);
for(int i=0; i<n; i++){
cin >> d[i];
}
int c;
cin >> c;
cout << find_shortcut(n, l, d, c) << "\n";
}*/
Compilation message
/usr/bin/ld: /tmp/cczYWunV.o: in function `main':
grader.cpp:(.text.startup+0x124): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
