题意：~ 思路：先处理出乘坐出租车能到达的点，建图跑最短路即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 100010; const LL INF = 1e18 + 7; const int lowINF...

题目链接：点我~~ 题意：1000个点10000条边的无向图，敌人从n走一条最短路到1，在第i条路设置障碍的代价是wi，求最少的代价使得敌人至少会遇到一次障碍。 思路：先确定最短路，然后在最短路径上跑一个网络流，即可求出最小割。 #include <bits/stdc++.h> using namespace std; typedef lon...

题意：n个点，m条边，构建有权无向图。求出删去最少条边数没有最短路，以及删出最多条边，使最短路的长度不变。 思路：先处理出最短路，然后使用结果的dis数组，若dis[v]-dis[u] = w(u,v)，则该路就是最短路经中的一条边。建出最短路径之后跑最大流，流量是有多少边权相同的重边，跑出来就是最小割，也就是阻断所有最短路的最小花费。最后再跑最短路，边权为...

将每个字符串的前后四位取出，如果A串的后面四位跟B串的前面四位相等，说明A可以通往B，然后以此建图，直接跑最短路就可以了 #include<iostream> #include<cstdio> #include<string> #include<string.h> #include<algorithm&g...