#include "shortcut.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
long long BIG = (long long) 1 << 62;
long long best = BIG;
vector<vector<pair<int, long long> > > adjacent (n, vector<pair<int, long long> > ());
for (int i = 0; i < n - 1; i++){
adjacent[i].push_back(make_pair(i + 1, l[i]));
adjacent[i + 1].push_back(make_pair(i, l[i]));
}
for (int s = 0; s < n; s++){
for (int e = s + 1; e < n; e++){
//Express line between s and e.
//Longest path in [0, s].
long long diameter = 0;
//
// long long b1 = d[0];
// long long b1_partial = d[0];
//
// for (int i = 1; i <= s; i++){
// b1_partial += l[i - 1];
// b1 = max(b1_partial + d[i], b1);
// b1_partial = max(b1_partial, d[i]);
// }
//
// diameter = max(diameter, b1);
//
// long long bn = d[n - 1];
// long long bn_partial = d[n - 1];
//
// for (int i = n - 1; i >= e; i--){
// bn_partial += l[i - 1];
// bn = max(bn_partial + d[i], bn);
// bn_partial = max(bn_partial, d[i]);
// }
//
// diameter = max(diameter, bn);
//
// long long bs = 0;
//
if (e != s + 1){
adjacent[s].push_back(make_pair(e, c));
adjacent[e].push_back(make_pair(s, c));
} else {
adjacent[s].pop_back();
adjacent[e].pop_back();
if (s > 0){
adjacent[s].pop_back();
adjacent[s].push_back(make_pair(s - 1, l[s - 1]));
}
if (e < n - 1){
adjacent[e].pop_back();
adjacent[e].push_back(make_pair(e + 1, l[e]));
}
adjacent[s].push_back(make_pair(e, min(l[s], c)));
adjacent[e].push_back(make_pair(s, min(l[s], c)));
}
for (int a = 0; a < n; a++){
priority_queue<pair<long long, int> > to_visit;
vector<long long> visited (n, -1);
to_visit.push(make_pair(-d[a], a));
visited[a] = -1;
diameter = max(diameter, (long long) d[a]);
while (!to_visit.empty()){
pair<long long, int> current_p = to_visit.top();
int current = current_p.second;
to_visit.pop();
if (visited[current] == -1){
visited[current] = -current_p.first;
//cout << s<< ' ' << e << ' ' << a << ' ' << current << ' ' << visited[current] << ' ' << d[current]<< endl;
if (current != a){
diameter = max(diameter, visited[current] + d[current]);
}
for (int i = 0; i < adjacent[current].size(); i++){
int next = adjacent[current][i].first;
//cout << 'n' << next << endl;
if (visited[next] == -1){
pair<long long, int> n;
n.first = -visited[current] - adjacent[current][i].second;
n.second = next;
to_visit.push(n);
//cout << endl << n.first << ' ' << n.second << endl;
}
}
}
}
}
adjacent[s].pop_back();
adjacent[e].pop_back();
if (e == s + 1){
adjacent[s].push_back(make_pair(e, l[s]));
adjacent[e].push_back(make_pair(s, l[s]));
}
//cout << diameter << ' ' << endl << endl;
best = min(best, diameter);
}
}
return best;
}
