[ABC416E] Development 題解

DengDuck · 2025-07-27 19:55:59 · 题解

笨蛋，這個數據範圍一看就是讓 \mathcal O(n^3+n^2q) 通過的啦，一看就是 Floyd 啦！

真是雜魚，這個機場本質上不就是建一個虛點 0，然後讓 0 和所有機場之間建立一個 \dfrac T 2 的雙向邊就可以了嗎！小數怎麼做？笨蛋！直接邊權都乘上 2 最後再除掉就可以了啊（臉紅，氣鼓鼓）！這樣，不就只有加邊操作了嗎！

嗚嗚嗚，可是我完全不知道應該怎麼支持修改操作啊！

什麼？按照邊考慮？可是 Floyd 難道不是這樣的......嗚嗚？什麼？居然是對的？騙人的吧！注意到加邊 u\to v 能給 F_{i,j} 帶來變化的要求是新的最短路進過了 u\to v，所以要麼是 i\to \cdots \to u\to v\to \cdots \to j 要麼是 i\to \cdots \to v\to u\to \cdots \to j，這個直接枚舉 i,j 就可以更新 F_{i,j} 了！

嗚嗚，已經完全要忘記 Floyd 的形狀了......

想看代碼嗎？好吧，就給你一個人看哦......

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=505;
const LL Inf=1e18;
int n,m,k;
LL F[N][N],T;
inline void Upd(int x,int y,LL w)
{
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)F[i][j]=F[j][i]=min({F[i][j],F[i][x]+w+F[y][j],F[i][y]+w+F[x][j]});
}
inline void Work()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)if(i!=j)F[i][j]=Inf;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        F[u][v]=F[v][u]=min(F[u][v],w*2ll);
    }
    cin>>k>>T;
    for(int i=1,x;i<=k;i++)
    {
        cin>>x;
        F[x][0]=F[0][x]=T;
    }
    for(int k=0;k<=n;k++)
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)F[i][j]=min(F[i][j],F[i][k]+F[k][j]);
    int Q;cin>>Q;
    for(int i=1,o,x,y,w;i<=Q;i++)
    {
        cin>>o;
        if(o==1)
        {
            cin>>x>>y>>w;
            F[x][y]=F[y][x]=min(F[x][y],w*2ll);
            Upd(x,y,w*2);
        }
        if(o==2)
        {
            cin>>x;
            F[x][0]=F[0][x]=T;
            y=0;
            Upd(x,y,T);
        }
        if(o==3)
        {
            LL Ans=0;
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)if(F[i][j]!=Inf)Ans+=F[i][j];
            cout<<Ans/2<<endl;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;T=1;
    while(T--)Work();
}