// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1000000500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m;
vector<vector<array<int, 2> > > adj;
vector<array<int,3> > edges;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
adj.assign(N + 1, vector<array<int,2> >());
n = N; m = M;
edges.resize(M);
for(int i = 0; i < m; i++) {
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
edges[i] = {U[i], V[i], W[i]};
}
}
void dijkstra(int src, vector<int> &sp, vector<vector<array<int,2> > > &ad, vector<int> &pr) {
priority_queue<array<int,2>, vector<array<int,2> >, greater<array<int,2> > > pq;
sp.assign(n, INF);
pr.assign(n, -1);
pq.push({0, src});
while(pq.size()) {
auto cur = pq.top();
pq.pop();
if(sp[cur[1]] != INF) {
continue;
}
// cout << cur[1] << " :" << cur[0] << "\n";
sp[cur[1]] = cur[0];
for(auto c : ad[cur[1]]) {
if(sp[c[0]] != INF) continue;
pq.push({max(cur[0] , c[1]), c[0]});
pr[c[0]] = cur[1];
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
vector<int> sp, pr;
dijkstra(X, sp, adj, pr);
int cost = sp[Y];
int ext = INF;
int x = Y;
vector<vector<array<int,2> > > tmp;
tmp = adj;
int cost2 = sp[Y];
while(x != X) {
// cout << x << " " << pr[x] << endl;
assert(pr[x] != -1);
for(auto itr = tmp[x].begin(); itr != tmp[x].end(); itr++) {
if((*itr)[0] == pr[x]) {
tmp[x].erase(itr);
break;
}
}
for(auto itr = tmp[pr[x]].begin(); itr != tmp[pr[x]].end(); itr++) {
if((*itr)[0] == x) {
tmp[pr[x]].erase(itr);
break;
}
}
x = pr[x];
}
x = pr[Y];
while(x != X) {
for(auto c : tmp[x]) {
ext = min(ext, c[1]);
}
x = pr[x];
}
cost = max(cost, ext);
dijkstra(X, sp, tmp, pr);
cost2 = max(cost2, sp[Y]);
if(min(cost2, cost) == INF) return -1;
// cout << endl;
return min(cost2, cost);
}
Compilation message
/usr/bin/ld: /tmp/cchPDnH1.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x217): undefined reference to `getMinimumFuelCapacity(int, int)'
collect2: error: ld returned 1 exit status
