【1】做题心得 - 2025 NOIP #65 - T2【凸包】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+10;
vector<array<ll,3>>e[N],g[N];
int n,m,Q,stk[N],top;
ll dep[N],dep2[N],k,ans,x[N],y[N],tot;
bool vis[N];
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
void dij(ll dep[],vector<array<ll,3>>E[],int ty){
	for(int i=1;i<=n;i++)
		dep[i]=1e18, vis[i]=0;
	q.push({0,(ty?n:1)});
	dep[(ty?n:1)]=0;
	while(q.size()){
		auto f=q.top();
		ll p=f.second,d=f.first;
		q.pop();
		if(vis[p]) continue;
		vis[p]=1;
		for(auto ED:E[p]){
			int v=ED[0];
			ll w=ED[1];
			if(d+w<dep[v]){
				dep[v]=d+w;
				if(!vis[v]) q.push({dep[v],v});
			}
		}
	}
	return;
}
void solve(){
	for(int i=1;i<=n;i++)
		e[i].clear(),
		g[i].clear();
	cin>>n>>m;
	bool wt=1;
	tot=0;
	for(int i=1;i<=m;i++){
		ll u,v,w,t;
		cin>>u>>v>>t>>w;
		e[u].push_back({v,t,w});   
		g[v].push_back({u,t,w}); 
		x[++tot]=w, y[tot]=1e18;
		wt&=(w==1);
	}
	sort(x+1,x+tot+1);
	tot=unique(x+1,x+tot+1)-x-1;
	dij(dep,e,0);
	dij(dep2,g,1);
	for(int u=1;u<=n;u++)for(auto ED:e[u]){
		int v=ED[0]; ll t=ED[1], w=ED[2];
		w=lower_bound(x+1,x+tot+1,w)-x;
		y[w]=min(y[w],dep[u]+t+dep2[v]);
	}
	top=0;
	for(int i=1;i<=tot;i++){
		while(top>=2){
			ll ya=y[stk[top]],yb=y[stk[top-1]],
			   xa=x[stk[top]],xb=x[stk[top-1]];	
			if((ya-yb)*(__int128)(x[i]-xa)>(xa-xb)*(__int128)(y[i]-ya))
				--top;
			else break;
		}
		stk[++top]=i;
	}
	cin>>Q;
	while(Q--){         
		cin>>k;
		if(wt)cout<<dep[n]-k<<"\n";
		else{
			int l=0,r=top;
			while(l+1<r){
				int mid=(l+r)/2;
				if(y[stk[mid+1]]-y[stk[mid]]>k*(x[stk[mid+1]]-x[stk[mid]]))
					r=mid;
				else 
					l=mid;
			}
			cout<<y[stk[r]]-k*x[stk[r]]<<"\n";
		}
	}
	return ;
}
int main(){
	freopen("kiongozi.in","r",stdin);
	freopen("kiongozi.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}