# 今年最佳最短路题(Best shortest path question of the year)-其他

## 今年最佳最短路题(Best shortest path question of the year)

### 思路解析

• 当前最短时间 < s[j] 那我们必须要等到 s[j] 才能坐上车
• 当前最短时间 >= s[j] 那我们必须等到下一班车来或者恰好能够赶上一班车

### 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;
}

dij(1);

cout<<dis[n]<<" "<<cost[n]<<endl;

}
``````
————————

### General idea of the topic

An undirected graph is given. Each directed edge represents a railway. The time of passing through this road is t, and it will stop at each station (node). Each train has a departure time point X and a departure frequency f, that is, one vehicle is sent every f minutes and a ride value C. The shortest traffic time of 1-N is calculated, and the toll is as small as possible.

### Train of thought analysis

It is easy to think that the essence of this problem is to find the shortest path of 1-N, so we directly consider how to relax in the shortest path

We can consider it in two cases:

• The current minimum time is < s [J], then we have to wait until s [J] to get on the bus
• Current shortest time > = s[j] then we must wait until the next bus comes or just catch the first bus

We use priority in Dijkstra_ Queue to maintain DIS for the shortest time. Of course, we can also use pair & lt; pair,int> To maintain the minimum time DIS and the minimum cost at the same time

### AC code

``````#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;