题目大意
给定一张无向图,边带两个参数 \(c_i,d_i\),在 \(t\) 时间时经过第 \(i\) 条边所需的时间是 \(c_i+\lfloor\frac{d_i}{t+1}\rfloor\),求在时间 \(0\) 时出发,在每个点可以停留非负整数时间,从点 \(1\) 到点 \(n\) 所需的最短时间。
思路分析
首先,容易发现在时间 \(t\) 时经过第 \(i\) 条边后的总时间是:\(t+c_i+\lfloor\frac{d_i}{t+1}\rfloor\)。
那么不妨设函数 \(f(t)=t+c_i+\lfloor\frac{d_i}{t+1}\rfloor\),由均值不等式容易得 \(f(t)_{\min}=f(\sqrt{d_i}-1)\)。
也就是说,当我们想经过某一条边时,如果当前时间大于 \(\sqrt {d_i}-1\),那么不用等待直接通过,否则等到 \(\sqrt{d_i}-1\) 时再通过。
那么就可以使用普通的 Dijkstra 解决了。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
const int N=200100;
int n,m,idx=1,in1,in2,in3,in4;
int to[N],nxt[N],head[N];
int fa[N],vis[N];
int dis[N],c[N],d[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int u,int v,int x,int y){
idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;c[idx]=x;d[idx]=y;
}
struct Node{
int x,time;
bool operator < (const Node &b) const{
return time>b.time;
}
}now;
priority_queue <Node> q;
void Dijkstra(){
memset(dis,0x3f,sizeof dis);
dis[1]=0;q.push(Node{1,0});
while(!q.empty()){
now=q.top();q.pop();
if(vis[now.x]) continue;
vis[now.x]=1;
for(int i=head[now.x];i;i=nxt[i]){
int v=to[i],t;
if(now.time<=round(sqrt(d[i]))-1) t=round(sqrt(d[i]))-1;
else t=now.time; //判断通过时间
if(dis[v]>t+c[i]+d[i]/(t+1)){
dis[v]=t+c[i]+d[i]/(t+1);
q.push(Node{v,dis[v]});
}
}
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld%lld",&in1,&in2,&in3,&in4);
add(in1,in2,in3,in4);add(in2,in1,in3,in4);
fa[find(in1)]=find(in2);
}
if(find(1)!=find(n)){cout<<"-1\n";return 0;}//并查集判连通
Dijkstra();
cout<<dis[n]<<'\n';
return 0;
}
标签:Node,Rush,include,idx,int,题解,ABC204E,now,dis
From: https://www.cnblogs.com/TKXZ133/p/17457551.html