“新华三杯”第十届成都信息工程大学ACM程序设计竞赛（同步赛）L. 怎么走啊(最短路+二分 分段函数)

题目

登录—专业IT笔试面试备考平台_牛客网

思路来源

衡阳师范学院ac代码、pj学弟

题解

大致可以证明，在w从1e5减小到1的过程中，

之前某条反向边没有用到，现在需要用到反向边，也就是正向边用到的变少了

这样的变化有sqrt个，二分每个变化时的临界点，复杂度似乎是O(nsqrtnlognlogn)的

但是由于只关注1到n的最短路，临界点&二分的量级很难卡满，只能说O(能过)了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int ll
const int N=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef pair<int,int> pii;
int n,m,d[N],st[N],ans[N],pre[N];
vector<array<int,3>> g[N];
int dijkstra(int W){
    for(int i=1;i<=n;i++) st[i]=0,d[i]=1e18;
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push({0,1}); d[1]=0;
    while(!q.empty()){
        auto [dt,u]=q.top(); q.pop();
        if(st[u]) continue;
        st[u]=1;
        for(auto [j,w,f]:g[u]){
            int dis=dt;
            if(f) dis+=w*W;
            else dis+=w;
            if(d[j]>dis){
                d[j]=dis;
                pre[j]=u;
                q.push({d[j],j});
            }
        }
    }
    return d[n];
}
map<pii,int> mp;
int fun(){
    int cnt=0;
    for(int i=n;i;i=pre[i]) cnt+=mp[{pre[i],i}];
    return cnt;
}
void solve(){
    cin>>n>>m; 
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        g[u].push_back({v,w,0});
        g[v].push_back({u,w,1});
        mp[{u,v}]=0;
        mp[{v,u}]=w;
    }
    int L=1;
    while(L<=1e5){
        int l=L,r=1e5; 
        int dis=dijkstra(l),sum=fun();
        while(l<r){
            int mid=(l+r+1)>>1;
            if(dijkstra(mid)==dis+(mid-L)*sum) l=mid;
            else r=mid-1;
        }
        for(int i=L;i<=l;i++) ans[i]=dis+(i-L)*sum;
        L=l+1;
    }
    int q; cin>>q;
    while(q--){
        int W; cin>>W;
        cout<<ans[W]<<endl;
    }
}
signed main(){
    IOS;
    int _=1;
    //cin>>_;
    while(_--){
        solve();
    }
}