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

· · 题解

显然边只选一条，所以会有最短路为：

dis(1,u)+w(u,v)+dis(v,n)

求这个的最小值，由于 w(u,v)=w_i-kt_i，一次函数，以 w_i 为横坐标即可。所以这是一个凸包。考虑一个维护凸包的东西做即可。但是我不会 Slope。

#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;
}