E - Rush Hour 2
设函数f(t)=t+ci+di/(t+1);
易得当t=sqrt(di)-1时取最小
所以根据时间来做dij
当时间大于sqrt(di)-1时直接加入即可
同时用并查集来查看1和n是否联通即可
ac code：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
const int maxn=500050;
int n,m,s,cnt;
const int inf=1e18;
int dis[maxn],h[maxn],to[maxn],c[maxn],nxt[maxn],vis[maxn],d[maxn];
struct node{
int v,w;
friend bool operator <(node a,node b){
return a.w>b.w;
}
};
priority_queue<node>q;
int f[maxn];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void add(int a,int b,int c1,int d1){
to[++cnt]=b;
c[cnt]=c1;
d[cnt]=d1;
nxt[cnt]=h[a];
h[a]=cnt;
}
void dijkstra(){
for(int i=0;i<=n;i++)dis[i]=inf;
dis[s]=0;
node tmp;
tmp.v=s;tmp.w=0;q.push(tmp);
while(!q.empty()){
int u=q.top().v,nowt=q.top().w;q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=h[u];i;i=nxt[i]){
int t=nowt;
if(t<=round(sqrt(d[i]))-1)t=round(sqrt(d[i]))-1;
if(dis[to[i]]>t+c[i]+(d[i]/(t+1))){
dis[to[i]]=t+c[i]+(d[i]/(t+1));
tmp.w=dis[to[i]];
tmp.v=to[i];
q.push(tmp);
}
}
}
}
void solve(){
cin>>n>>m;
s=1;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1,u,v,w,k;i<=m;i++){
cin>>u>>v>>w>>k;
add(u,v,w,k);add(v,u,w,k);
f[find(u)]=find(v);
}
if(find(1)!=find(n)){cout<<-1;return;}
dijkstra();
cout<<dis[n];
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _=1;
// cin>>_;
while(_--)solve();
}