題目

登錄—專業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();}
}