#include "swap.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
/////////////////////////////////////////////////////
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); }
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int MAXA = 1e9 + 7;
int n, m;
array<int, 3> edge[M];
vector <int> a[N];
int ma = 0;
bool vis[N];
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
for(int i = 0; i < m; ++i){
edge[i] = {U[i], V[i], W[i]};
ma = max(ma, W[i]);
//a[U[i]].push_back({V[i], W[i]});
//a[V[i]].push_back({U[i], W[i]});
}
}
void bfs(vector <int> &d, int u, int ban = -1){
queue<int> q;
q.push(u);
while (!q.empty()){
int u = q.front(); q.pop();
for(int i : a[u]){
if (i == ban) continue;
if (d[i] == MAXA){
d[i] = d[u] + 1;
q.push(i);
}
}
}
}
bool f(int mid, int X, int Y){
for(int i = 0; i < n; ++i) a[i].clear();
for(int i = 0; i < m; ++i){
if (edge[i][2] <= mid) {
a[edge[i][0]].push_back(edge[i][1]);
a[edge[i][1]].push_back(edge[i][0]);
}
}
vector <int> d(n, MAXA);
d[X] = 0; bfs(d, X);
vector <int> dx(n, MAXA), dy(n, MAXA);
dx[X] = 0; bfs(dx, X, Y);
dy[Y] = 0; bfs(dy, Y, X);
//dbg(dx, 0, n - 1);
//dbg(dy, 0, n - 1);
int disxy = d[Y];
if (disxy >= MAXA) return false;
int ct = 0;
for(int i = 0; i < n; ++i){
if (dx[i] == MAXA || dy[i] == MAXA) continue;
++ct;
}
return (ct > disxy - 1);
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = MAXA;
while (l + 1 < r){
int mid = (l + r) >> 1;
if (f(mid, X, Y)) r = mid;
else l = mid;
}
if (r == MAXA) r = -1;
return r;
}
///////////////////////////////////////////////////////
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i) {
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i) {
printf("%d\n", minimum_fuel_capacities[i]);
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccTMVxFd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cconQuzg.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
