#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int, ll>>> adj;
int N;
ll find_diameter(int l, int r, int c)
{
adj[l].push_back({r, c});
adj[r].push_back({l, c});
ll diameter = 0;
for (int i = 0; i < N; i++)
{
vector<int> visited(N);
vector<ll> dist(N, 1ll << 60);
dist[i] = 0;
ll mxDist = 0;
priority_queue<pair<ll, int>> q;
q.push({0, i});
while (!q.empty())
{
int s = q.top().second;
q.pop();
if (visited[s]) continue;
visited[s] = 1;
mxDist = max(mxDist, dist[s]);
for (auto node : adj[s])
{
if (visited[node.first] || dist[s] + node.second > dist[node.first]) continue;
dist[node.first] = dist[s] + node.second;
q.push({-dist[node.first], node.first});
}
}
diameter = max(mxDist, diameter);
}
adj[l].pop_back();
adj[r].pop_back();
return diameter;
}
ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
N = 2 * n;
adj.resize(N);
for (int i = 0; i < n - 1; i++)
{
adj[i].push_back({i+1, l[i]});
adj[i+1].push_back({i, l[i]});
}
for (int i = 0; i < n; i++)
{
adj[i].push_back({i+n, d[i]});
adj[i+n].push_back({i, d[i]});
}
ll res = 1ll << 60;
for (int i = 0; i < n - 1; i++)
{
for (int j = i+1; j < n; j++)
{
res = min(res, find_diameter(i, j, c));
}
}
return res;
}
