原题链接：K-PP 学姐的最短时间
题目大意：给n个点和m条边，给每条边通过的时间为a+b/(t+1),t为从当前点出发的时间。求从第一点到第n个点的最短时间。
思路：这题明显是求最短路的题目，那么肯定可以使用迪杰斯特拉来跑最短路，但是二个点之间通过时间是动态的，那么如何来确定这个动态时间什么时候能最小呢？在i点的时间为t,然后i到j的通过时间为a+b/(t+1),那么就是比较停留在i点的时间和b/(t+1)能够提供的节省时间比较。可以分为3种情况考虑，如果b<t+1,那么就不需要等待，多等待一秒，b/(t+1)也是0。如果t+1>sqrt(b),那么多等待一秒，b/(t+1)能减少的最多也就1秒。如果t+1<sqrt(b),那么多等待一秒，b/(t+1)肯定会减少至少1,可以等待。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=1e6+10;
ll h[N],e[N],ne[N],w[N],p[N],idx,d[N];
bool st[N];
void add(ll a,ll b,ll c,ll d)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,p[idx]=d,h[a]=idx++;
}
ll calc(ll t,ll b)
{
if(b<t+1)//第一种情况
{
return 0;
}
else//对于第二种情况，肯定不能继续等，对于第三种情况一定要继续等，那么就可以枚举sqrt(b)周围的情况来找到最小的通过时间
{
ll ans=1e18;
for(int i=max(t,(ll)sqrt(b)-1);i<=max(t,(ll)sqrt(b)+1);i++)
{
ans=min(ans,i-t+b/(i+1));//i是从当前点出发的时间，t是到达当前点的时间
}
return ans;
}
}
int main()
{
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
ll n,m;cin>>n>>m;
memset(h,-1,sizeof(h));
while(m--)
{
ll a,b,c,d;cin>>a>>b>>c>>d;
add(a,b,c,d);add(b,a,c,d);
}
priority_queue<pii,vector<pii>,greater<pii>> op;
op.push({0,1});
memset(d,0x3f,sizeof(d));
d[1]=0;
while(op.size())
{
auto [vel,id]=op.top();op.pop();
if(st[id])continue;st[id]=1;
for(int i=h[id];~i;i=ne[i])
{
ll j=e[i],a=w[i],b=p[i];
ll d1=calc(vel,b);
if(d[j]>vel+d1+a)
{
d[j]=vel+d1+a;
op.push({d[j],j});
}
}
}
if(d[n]>1e17)cout<<-1;
else cout<<d[n];
return 0;
}