#include "swap.h" #include <vector> const int N = 100000, INF = 0x3f3f3f3f; int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int ww[N], n, m, ans, mn1, mn2, mn3, star; void init(int n_, int m_, std::vector<int> ii, std::vector<int> jj, std::vector<int> ww_) { int h, ans; n = n_, m = m_; ans = -1, star = 0; if (m == n - 1) { star = 1, ans = -1; for (h = 0; h < m; h++) if (ii[h] != 0) { star = 0; break; } mn1 = mn2 = mn3 = INF; for (h = 0; h < m; h++) { ww[jj[h]] = ww_[h]; if (mn1 > ww_[h]) mn3 = mn2, mn2 = mn1, mn1 = ww_[h]; else if (mn2 > ww_[h]) mn3 = mn2, mn2 = ww_[h]; else if (mn3 > ww_[h]) mn3 = ww_[h]; } ans = -1; } else for (h = 0; h < m; h++) ans = max(ans, ww_[h]); } int getMinimumFuelCapacity(int i, int j) { return star ? max(max(ww[i], ww[j]), mn3) : ans; }