floyd搞出两点间最短距离 二分判答案
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = ;
const int MAXM = ;
const ll INF = 1LL << ;
ll f[MAXM << ];
int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], ed = , S, T;
inline void read(ll &v)
{
v = ;
char c = ;
ll p = ;
while (c < '' || c > '') {
if (c == '-') {
p = -;
}
c = getchar();
}
while (c >= '' && c <= '') {
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
inline void addedge(int u, int v, ll cap)
{
to[++ed] = v;
nxt[ed] = Head[u];
Head[u] = ed;
f[ed] = cap;
to[++ed] = u;
nxt[ed] = Head[v];
Head[v] = ed;
f[ed] = ;
return;
}
inline bool BFS()
{
int u;
memset(lev, -, sizeof(lev));
queue<int>q;
lev[S] = ;
q.push(S);
while (q.size()) {
u = q.front();
q.pop();
for (int i = Head[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
q.push(to[i]);
/*
if (to[i] == T)
{
return 1;
}
magic one way optimize
*/
}
}
memcpy(cur, Head, sizeof Head);
return lev[T] != -;
}
inline ll DFS(int u, ll maxf)
{
if (u == T || !maxf) {
return maxf;
}
ll cnt = , tem;
for (int &i = cur[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == lev[u] + ) {
tem = DFS(to[i], min(maxf, f[i]));
maxf -= tem;
f[i] -= tem;
f[i ^ ] += tem;
cnt += tem;
if (!maxf) {
break;
}
}
if (!cnt) {
lev[u] = -;
}
return cnt;
}
ll Dinic()
{
ll ans = ;
while (BFS()) {
ans += DFS(S, 1LL << );
}
return ans;
}
void init(int SS, int TT)
{
memset(Head, , sizeof(Head));
ed = ;
S = SS;
T = TT;
return;
}
ll n, m;
ll u, v , c;
ll s[MAXN], p[MAXN];
ll dis[MAXN][MAXN];
ll sum = ;
bool check(ll x)
{
memset(Head, , sizeof(Head));
ed = ;
S = , T = * n + ;
for (int i = ; i <= n; i++) {
addedge(S, i, s[i]);
addedge(i + n, T, p[i]);
}
for (int i = ; i <= n; i++) {
for (int j = i; j <= n; j++) {
if (i == j) {
addedge(i, i + n, INF);
} else if (dis[i][j] <= x) {
addedge(i, j + n, INF), addedge(j, i + n, INF);
}
}
}
if (Dinic() == sum) {
return true;
}
return false;
}
int main()
{
ll x;
read(n), read(m);
for (int i = ; i <= n; i++) {
read(x), s[i] = x;
read(x), p[i] = x;
sum += s[i];
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
if (i == j) {
dis[i][j] = ;
} else {
dis[i][j] = 1LL << ;
}
}
}
for (int i = ; i <= m; i++) {
read(u), read(v), read(c);
dis[u][v] = dis[v][u] = min(dis[u][v], c);
}
for (int k = ; k <= n; k++)
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
ll l = INF, r = -INF, mid;
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
if (i != j) {
if (dis[i][j] >= INF) {
continue;
}
r = max(dis[i][j], r);
l = min(l, dis[i][j]);
}
}
}
r++, l--;
bool flag = false;
while (l < r - ) {
mid = (l + r) >> ;
if (check(mid)) {
r = mid;
flag = true;
} else {
l = mid;
}
}
if (flag) {
cout << r << endl;
} else {
cout << - << endl;
}
return ;
}