CF295B Greg and Graph

思路:考察了Floyd的变形使用,我们知道Floyd是在不断地枚举是否有一个点 k k k,然后用 k , 优化图中所有点对 ( i , j ) 的最短路 k,优化图中所有点对(i,j)的最短路 k,优化图中所有点对(i,j)的最短路. 在本题中,我们不可能每次删完一个点之后再跑一次最短路,考虑在上述做法中思考变形. 显然,k的枚举顺序是对原图没有影响的,这样,我们考虑倒序处理,就是把点逐个加入原图中,然后求最短路,那么Floyd的算法会有影响吗,答案是没有的,因为Floyd三重循环里边,是枚举一个没有被用过的点,尝试用它去优化其他点的最短路,那么,我们就用新加入的点作为k,剩下的 i , j i,j i,j按原算法执行即可.

#include
using namespace std;
const int maxn = 500+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
bool vis[maxn];ll g[maxn][maxn];ll ans[maxn];int x[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;ig[i][j];
	}
	for(int i=1;i>x[i];
	for(int i=n;i>=1;i--){
		int k = x[i];vis[k] = 1;
		for(int i=1;i