前言

十年 OI 一场空，不开 long long 见祖宗。这是我第一次洛谷的官方题解。

题目大意

给你一个 $N$ 个点，$M$ 条边的无向图，图中有 $K$ 个点有机场，有机场的点可以耗时 $T$ 时抵达另一个有机场的点。

有 $Q$ 个查询，分为 $3$ 种:加边、加机场、询问所有联通的点之间的最短距离之和。

分析

注意到 $N\leq500$，还要求最短路、加边，我们可以直接使用邻接矩阵存图，并用 Floyd 计算多源最短路。

使用 Floyd 进行加边操作很简单，假设加上了连接 $u,v$ 长度为 $w$ 的边，状态转移方程如下：

$$dis_{i,j}=min{dis_{i,j},dis_{i,u}+w+dis_{v,j},dis_{i,v}+w+dis_{u,j}}$$

但是添加机场应该怎么处理呢？其实很简单（虽然我在比赛的时候 D 没开 long long 调了好久导致E没时间）。

可以添加一个虚点 $N+1$，让这个点与所有有机场的点连接一条长为 $\frac{T}{2}$ 的边。有点新建机场时，只需让它与 $N+1$ 连边，即转化为加边操作，如上述方程转移即可。

为了避免浮点数一开始先将边权乘以 $2$，最后计算时再除以 $2$。

代码

（上一题没开 long long 有阴影了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=505;
int n,m,g[N][N],k,t;
void add(int u,int v,int w){
    for(int i=1;i<=n+1;i++)
        for(int j=1;j<=n+1;j++)
            g[i][j]=min({g[i][j],g[i][u]+w+g[v][j],g[i][v]+w+g[u][j]}); 
} 
signed main(){
    memset(g,0x3f,sizeof(g));
    int inf=g[0][0];
    cin>>n>>m;
    for(int i=1;i<=n+1;i++) g[i][i]=0;
    while(m--){
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        g[u][v]=g[v][u]=min(g[u][v],w*2);
    } 
    cin>>k>>t;
    int d;
    for(int i=1;i<=k;i++) scanf("%lld",&d),g[d][n+1]=g[n+1][d]=t; //机场n+1 
    for(int k=1;k<=n+1;k++)//floyd
        for(int i=1;i<=n+1;i++)
            for(int j=1;j<=n+1;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    int q,op;
    cin>>q;
    while(q--){
        scanf("%lld",&op);
        if(op==1){
            int u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            add(u,v,2*w);
        }
        else if(op==2){
            int x;
            scanf("%lld",&x);
            add(x,n+1,t);
        }
        else{
            int tot=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(g[i][j]!=inf) tot+=g[i][j]/2;
            printf("%lld\n",tot);
        }
    } 
    return 0;
}