衡阳师范学院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();
}
}