专栏文章

[ABC416E] Development 題解

DDengDuck鄧德
AT_abc416_e题解参与者 25已保存评论 24

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
24 条
当前快照
1 份
快照标识符
@miop3hfu
此快照首次捕获于
2025/12/02 22:50
3 个月前
此快照最后确认于
2025/12/02 22:50
3 个月前
查看原文
笨蛋，這個數據範圍一看就是讓 O(n3+n2q)\mathcal O(n^3+n^2q) 通過的啦，一看就是 Floyd 啦！
真是雜魚，這個機場本質上不就是建一個虛點 00，然後讓 00 和所有機場之間建立一個 T2\dfrac T 2 的雙向邊就可以了嗎！小數怎麼做？笨蛋！直接邊權都乘上 22 最後再除掉就可以了啊（臉紅，氣鼓鼓）！這樣，不就只有加邊操作了嗎！
嗚嗚嗚，可是我完全不知道應該怎麼支持修改操作啊！
什麼？按照邊考慮？可是 Floyd 難道不是這樣的......嗚嗚？什麼？居然是對的？騙人的吧！注意到加邊 u→vu\to v 能給 Fi,jF_{i,j} 帶來變化的要求是新的最短路進過了 u→vu\to v，所以要麼是 i→⋯→u→v→⋯→ji\to \cdots \to u\to v\to \cdots \to j 要麼是 i→⋯→v→u→⋯→ji\to \cdots \to v\to u\to \cdots \to j，這個直接枚舉 i,ji,j 就可以更新 Fi,jF_{i,j} 了！
嗚嗚，已經完全要忘記 Floyd 的形狀了......
想看代碼嗎？好吧，就給你一個人看哦......
CPP
#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();
}

评论

共 24 条评论，欢迎与作者交流。

正在加载评论...