本文主要是介绍西理工校赛：PP 学姐的最短时间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：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;
}这篇关于西理工校赛：PP 学姐的最短时间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
