#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, multiset<pair<int, int>>());
for (int i = 0; i + 1 < n; i++)
{
adj[i].insert({i + 1, l[i]});
adj[i + 1].insert({i, l[i]});
}
for (int i = 0, j = 0; i < n; i++)
{
if (d[i] == 0)
continue;
adj[i].insert({n + j, d[i]});
adj[n + j].insert({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])
pq.push({c + w, v});
}
return mx;
};
vector<int> edge;
for(int i = 0, j = 0; i < n; i++)
{
if(d[i] == 0)
continue;
edge.push_back(n + j);
j++;
}
vector<int> edges;
// if(not edge.empty())
// {
// edges.push_back(edge.front());
// if((int)edge.size() > 1)
// edges.push_back(edge.back());
// }
for(auto i: edge)
edges.push_back(i);
if(d[0] == 0)
edges.push_back(0);
if(d[n - 1] == 0)
edges.push_back(n - 1);
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
adj[i].insert({j, C});
adj[j].insert({i, C});
long long mx = 0;
for (auto k: edges)
{
long long s = bfs(k);
if (mx < s)
mx = s;
}
if (mn > mx)
mn = mx;
adj[i].erase(adj[i].find({j, C}));
adj[j].erase(adj[j].find({i, C}));
}
}
return mn;
}
