#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
long long find_shortcut(int n, vector<int> l, vector<int> d, int C)
{
int cnt = count_if(d.begin(), d.end(), [&](int x)
{ return x > 0; });
vector adj(n + cnt, vector<pair<int, int>>());
for (int i = 0; i + 1 < n; i++)
{
adj[i].push_back({i + 1, l[i]});
adj[i + 1].push_back({i, l[i]});
}
for (int i = 0, j = 0; i < n; i++)
{
if (d[i] == 0)
continue;
adj[i].push_back({n + j, d[i]});
adj[n + j].push_back({i, d[i]});
j++;
}
long long mn = 1e18 + 10;
vector<long long> dis(n + cnt);
auto bfs = [&](int start) -> long long
{
pqg<pair<long long, int>> pq;
dis.assign(n + cnt, 1e18 + 10);
pq.push({0, start});
long long mx = 0;
while (not pq.empty())
{
auto [c, u] = pq.top();
pq.pop();
if (dis[u] <= c)
continue;
dis[u] = c;
mx = max(mx, dis[u]);
for (auto [v, w] : adj[u])
if(dis[v] > c + w)
pq.push({c + w, v});
}
return mx;
};
set<int> edge;
bfs(0);
int xx = max_element(dis.begin(), dis.end()) - dis.begin();
bfs(xx);
xx = max_element(dis.begin(), dis.end()) - dis.begin();
bfs(xx);
priority_queue<pair<long long, int>> pq;
for(int i = 0; i < n + cnt; i++)
pq.push({dis[i], i});
int y = min((int)pq.size(), 6);
while(y--)
{
auto [c, v] = pq.top();
pq.pop();
edge.insert(v);
}
while(not pq.empty())
{
pq.pop();
}
xx = max_element(dis.begin(), dis.end()) - dis.begin();
bfs(xx);
for(int i = 0; i < n + cnt; i++)
pq.push({dis[i], i});
y = min((int)pq.size(), 6);
while(y--)
{
auto [c, v] = pq.top();
pq.pop();
edge.insert(v);
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
adj[i].push_back({j, C});
adj[j].push_back({i, C});
long long mx = 0;
for (auto k: edge)
{
long long s = bfs(k);
if (mx < s)
mx = s;
}
if (mn > mx)
mn = mx;
adj[i].pop_back();
adj[j].pop_back();
}
}
return mn;
}
