#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e18;
ll N;
ll nodes;
vvpll g;
ll find() {
ll ans = 0;
loop(s, 0, nodes) {
vll dist(nodes, inf);
dist[s] = 0;
priority_queue<pll, vpll, greater<pll>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : g[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
loop(i, 0, nodes) {
ans = max(ans, dist[i]);
}
}
return ans;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
ll cnt =n ;
g.resize(n*2);
loop(i,0,n-1) {
g[i].push_back({i+1, l[i]});
g[i+1].push_back({i, l[i]});
if (d[i]) {
g[i].push_back({cnt, d[i]});
g[cnt].push_back({i, d[i]});
cnt++;
}
}
if (d[n-1]) {
g[n-1].push_back({cnt, d[n-1]});
g[cnt].push_back({n-1, d[n-1]});
cnt++;
}
N=n;
ll ans = inf;
nodes = cnt;
loop(i,0,n) {
loop(j,i+1, n) {
g[i].push_back({j,c});
g[j].push_back({i,c});
ans = min(ans, find());
g[i].pop_back();
g[j].pop_back();
}
}
return ans;
}
/*
4 10
10 20 20
0 40
0 30
*/
