题目-[ABC416E] Development
算法关键词：图论，最短路
题目大意：一张图有 \(n\) 个节点和 \(m\) 条无向边，边权为 \(m_i\)，其中有 \(k\) 个特殊节点，每个特殊节点间有一条边权为 \(T\) 的无向边。问\(\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)\)。（\(f(x,y)\)代表从 \(x\) 城市到 \(y\) 城市的最短路）。
很显然这道题和最短路密切相关 （没有什么乱搞成分），又因为需要求全源最短路，看眼数据范围只到 \(0 \le n \le 500\)，可以放心选择floyd。但显然不能每次操作都重新建图（时间复杂度来到 \(O(Qn^3)\)）。那么我们该怎么办呢OvO？
既然每次添加的长度都相同，那么我们不妨假设每一次建设飞机场都相当于连接到一个“中心节点”（当然这个点是不存在的），这样每次建设飞机场都转换成了新建一条边，就很好实现了，时间复杂度在\(O(Qn^2)\)，可以接受。
代码实现，额码力还是太差了。
#include<bits/stdc++.h>
using namespace std;
int floyd[505][505];
int main(){int n,m,Q,T;cin>>n>>m;for(int i=1;i<=n+1;i++)for(int j=1;j<=n+1;j++)if(i!=j)floyd[i][j]=1e18;while(m--){int u,v,w;cin>>u>>v>>w;w*=2;floyd[u][v]=min(floyd[u][v],w);floyd[v][u]=min(floyd[v][u],w);}cin>>m>>T;while(m--){int u=n+1,v,w=T;cin>>v;floyd[u][v]=min(floyd[u][v],w);floyd[v][u]=min(floyd[v][u],w);}for(int k=1;k<=n+1;k++)for(int i=1;i<=n+1;i++)for(int j=1;j<=n+1;j++)floyd[i][j]=min({floyd[i][j],floyd[i][k]+floyd[k][j]});cin>>Q;while(Q--){int op;cin>>op;if(op==1){int u,v,w;cin>>u>>v>>w;w*=2;for(int j=1;j<=n+1;j++)for(int k=j+1;k<=n+1;k++)floyd[k][j]=floyd[j][k]=min({floyd[j][k],floyd[j][u]+floyd[v][k]+w,floyd[j][v]+floyd[u][k]+w});}else if(op==2){int u=n+1,v,w=T;cin>>v;for(int j=1;j<=n+1;j++)for(int k=j+1;k<=n+1;k++)floyd[k][j]=floyd[j][k]=min({floyd[j][k],floyd[j][u]+floyd[v][k]+w,floyd[j][v]+floyd[u][k]+w});}else{int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(floyd[i][j]!=1e18)ans+=floyd[i][j];cout<<ans/2<<endl;}}return 0;
}