#include <bits/stdc++.h>
#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include "shortcut.h"
#endif
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> dijkstra(int s)
{
vector<int> dist(adj.size(), -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s});
while (!pq.empty())
{
auto [d, i] = pq.top();
pq.pop();
if (dist[i] != -1)
continue;
dist[i] = d;
for (auto [c, p] : adj[i])
{
if (dist[c] == -1)
pq.push({d + p, c});
}
}
return dist;
}
long long dia()
{
vector<int> dists;
dists = dijkstra(0);
dists = dijkstra(max_element(dists.begin(), dists.end()) - dists.begin());
return *max_element(dists.begin(), dists.end());
}
long long plan_roller_coaster(int n, vector<int> l, vector<int> d, int c)
{
adj = vector<vector<pair<int, int>>>(2 * 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]});
}
long long best = dia();
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});
best = min(best, dia());
adj[i].pop_back();
adj[j].pop_back();
}
return best;
}
#ifdef _DEBUG
int main() {
int n, c;
cin >> n >> c;
vector<int> l(n-1);
vector<int> d(n);
for(int & x : l)
cin >> x;
for (int& x : d)
cin >> x;
cout << plan_roller_coaster(n, l, d, c);
}
#endif
Compilation message
/usr/bin/ld: /tmp/ccId28f3.o: in function `main':
grader.cpp:(.text.startup+0x124): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
