T1 图论题

从 s 和 t 分别跑个最短路，然后建出到 s 的凸包，用 t 二分去就行了

从 s 跑 k 次同时维护李超树可以求出连 k 条边的最优解

T2 构造题

没想懂细节

T3 数据结构题

因为是顺序改题，就没有然后了，，，

代码

T1

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
const int N=200011;
const int inf=1e18;
struct bag_{int x,y;friend bool operator<(bag_ a,bag_ b){return a.x!=b.x?a.x<b.x:a.y>b.y;}}now;
struct e_{int v,w;friend bool operator<(e_ a,e_ b){return a.w>b.w;}};
bool jud[N];
int n,m,s,t;
int d[2][N];
vector<e_> v[2][N];
vector<bag_> bag;
priority_queue<e_> dui;
il int min_(int x,int y){return x>y?y:x;}
il double get_xl(bag_ a,bag_ b){return (b.y-a.y)/(b.x-a.x);}
il bool jd(bag_ a,bag_ b,bag_ c){return (b.x==c.x)||get_xl(a,c)>=get_xl(b,c);}
il int get_ans(bag_ a,int x){return x*x+a.y-2*a.x*x;}
il int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void dij(int x,bool jd)
{
	memset(d[jd],0x3f,sizeof(d[jd]));
	memset(jud,0,sizeof(jud));
	d[jd][x]=0;
	dui.push({x,0});
	e_ u;
	while(dui.size())
	{
		u=dui.top(),dui.pop();
		if(jud[u.v]) continue;
		jud[u.v]=1;
		for(e_ y : v[jd][u.v])
			if(d[jd][y.v]>d[jd][u.v]+y.w)
			{
				d[jd][y.v]=d[jd][u.v]+y.w;
				dui.push({y.v,d[jd][y.v]});
			}
	}
	return;
}
int two(int x)
{
	int sz=bag.size();
	if(sz==0) return inf;
	if(sz==1) return get_ans(bag[0],x);
	if(sz==2) return min_(get_ans(bag[0],x),get_ans(bag[1],x));
	if(get_ans(bag[0],x)<get_ans(bag[1],x)) return get_ans(bag[0],x);
	if(get_ans(bag[sz-1],x)<get_ans(bag[sz-2],x)) return get_ans(bag[sz-1],x);
	int l=1,r=sz-2,mid=1,ans=inf,ansl,ansr;
	while(l<=r)
	{
		mid=(l+r)>>1;
		ansl=get_ans(bag[mid],x);
		ansr=get_ans(bag[mid+1],x);
		if(ansl<ansr) r=mid-1;
		else l=mid+1;
		ans=min_(ans,min_(ansl,ansr));
	}
	ans=min_(ans,get_ans(bag[mid],x));
	ansl=get_ans(bag[mid-1],x);
	ansr=get_ans(bag[mid+1],x);
	return min_(ans,min_(ansl,ansr));
}
signed main()
{
//	freopen("c.in","r",stdin);
//	freopen("zj1.out","w",stdout);
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	n=read(),m=read(),s=read(),t=read();
	for(int x,y,z,i=1;i<=m;++i)
	{
		x=read(),y=read(),z=read();
		v[0][x].push_back({y,z});
		v[1][y].push_back({x,z});
	}
	dij(s,0),dij(t,1);
	int sz=0;
	for(int y,x,i=1;i<=n;++i)
	{
		if(d[1][i]==0x3f3f3f3f3f3f3f3f)continue;
		x=i,y=d[1][i]+i*i;
		now=(bag_){x,y};
		while(sz>1&&jd(bag[sz-2],bag[sz-1],now)) --sz,bag.pop_back();
		bag.push_back(now),++sz;
	}
	int ans=inf;
	for(int i=1;i<=n;++i) ans=min_(ans,d[0][i]+two(i));
	cout<<ans<<endl;
	return 0;
}