今年最佳最短路题
2021/11/24 23:40:22
本文主要是介绍今年最佳最短路题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接 J. Jinping Trains
题目大意
给出一张无向图,每条有向边表示一条铁路,通过这条路的时间为t,到每个站点(节点)都会停靠,每列车都有一个发车时间点x,有一个发车频率f,即每f分钟发一辆车,一个乘坐价值c,求出1-n最短的交通时间并且路费尽量小。
思路解析
我们很容易会想到这道题的本质就是求1-n的最短路,所以我们就直接考虑最短路中如何进行松弛操作
我们可以分成两种情况来考虑:
- 当前最短时间 < s[j] 那我们必须要等到 s[j] 才能坐上车
- 当前最短时间 >= s[j] 那我们必须等到下一班车来或者恰好能够赶上一班车
我们在dijkstra中用priority_queue来维护dis最短时间,当然我们也可以用pair<pair,int>来同时维护最短时间dis和最小花费cost
AC代码
#include<bits/stdc++.h> #include <utility> using namespace std; typedef long long ll; typedef unsigned long long ull; #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #define endl '\n' #define pii pair<pair<int,int>,int> #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int maxn=1e6+5; int n,m; int e[maxn],nex[maxn],h[maxn],w[maxn],id; int dis[maxn],cost[maxn],vis[maxn]; int c[maxn],f[maxn],s[maxn]; void add(int x,int y,int z,int xx,int yy,int zz){ e[++id]=y; w[id]=z; c[id]=xx; f[id]=yy; s[id]=zz; nex[id]=h[x]; h[x]=id; } void dij(int x){ priority_queue<pii,vector<pii>,greater<pii> >q; memset(dis,0x3f,sizeof dis); dis[x]=s[0]; q.push({make_pair(0,0),x}); while(q.size()){ int top=q.top().second; q.pop(); if(vis[top])continue; vis[top]=1; for(int i=h[top];i;i=nex[i]){ int j=e[i],tt=0; if(dis[top]<s[i])tt=s[i]+w[i]; else { tt=(dis[top]-s[i])/f[i]+1; tt=tt*f[i]+s[i]+w[i]; } if(dis[j]>tt||(dis[j]==tt&&cost[j]>cost[top]+c[i])){ dis[j]=tt; cost[j]=cost[top]+c[i]; q.push({make_pair(dis[j],cost[j]),j}); } } } } int main(){ IOS cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,t,x,y,z; cin>>u>>v>>t>>x>>y>>z; add(u,v,t,x,y,z); } dij(1); cout<<dis[n]<<" "<<cost[n]<<endl; }
这篇关于今年最佳最短路题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程