算法题求解！最短路径+动态规划 C++
题目设计：
你怀疑你的导航系统有时会选择低效的路线。
所以你决定收集一些关于你所在地区的道路系统的数据并编写一个程序，计算出从你的家到你所在地区的最短（综合道路长度）和最快（预期旅行时间）的路线。
为了使这一任务易于管理，你想出了一个简单的模型。道路系统道路系统由路口（数字从1到N）和连接它们的道路组成，每条道路都有一个限速（单位：km/h）和一个长度（单位：km）。
在其中一个路口转换道路既不耗费时间也不耗费距离。
为了简单起见，你还假设所有的道路都是双向的，并且你可以一直以限速行驶。
输入的内容包括
- 一行包含N和M(2 ≤ N ≤ 5 · 10^4^, 1 ≤ M ≤ 2 · 10^5^) --分别表示路口和道路的数量
- M行描述道路，第 i 行包含bi, ei, vi和 i (1 ≤ bi，ei≤N，20≤vi≤150，1≤ i ≤300）分别代表第i条道路，与其连接的路口，速度限制和长度（所有这些输入都是整数)
- 一行包含 Q（1 ≤ Q ≤ 1000）--查询的数量
- Q行给出查询，每行包括一个整数 j：目的地路口的索引和一个字符c∈{'s', 'f'}
输出
- 对于's'类型的查询，输出从你的家（1号路口）到指定目的地的最短路线的长度。
- 对于'f'类型的查询，输出从你的家到指定目的地的最短旅行时间（假设一直按限速行驶），精度为10^-3^
- 使用与输入相同的单位，用空格分隔数量和单位。如果一个给定的目的地不能到达，输出 "IMPOSSIBLE"。
例如：
第三组：
20 80
19 15 57 179
20 20 125 175
5 4 60 34
9 10 24 85
18 8 114 244
19 9 23 245
1 5 115 132
7 17 45 117
6 12 24 109
1 12 116 83
3 3 83 270
20 20 145 65
9 13 78 47
11 14 40 152
9 15 79 70
18 9 72 101
19 5 105 282
2 3 120 90
20 13 105 186
2 4 72 145
13 18 103 90
1 3 26 143
19 13 45 7
5 14 39 295
9 7 74 218
15 5 73 131
6 15 79 255
6 15 56 113
14 5 40 157
17 17 57 216
17 14 106 260
18 9 121 201
7 11 76 25
14 17 20 144
10 6 49 285
6 16 88 95
6 4 82 96
10 16 121 187
19 11 100 294
6 9 129 241
4 4 90 99
11 15 79 130
5 8 95 108
19 15 29 285
19 20 122 280
19 13 76 13
12 16 67 88
18 10 107 56
2 18 147 300
6 15 27 130
16 6 80 28
8 5 101 96
16 16 76 130
12 3 134 1
17 4 145 284
14 9 24 203
5 13 39 140
12 9 116 254
5 12 141 52
16 3 68 95
17 1 44 14
12 20 62 161
18 16 129 72
16 18 117 114
20 17 128 271
2 1 92 255
1 19 74 115
15 2 57 240
18 7 41 140
14 1 107 280
4 6 66 205
6 10 60 209
17 2 112 42
8 2 45 14
7 16 59 33
13 16 40 270
17 6 41 59
4 13 57 245
19 11 55 97
2 8 115 80
10
2 s
15 f
7 s
17 f
8 f
9 f
17 s
16 f
2 s
3 f
输出：
56 km
2.87883212 h
131 km
0.31818182 h
1.00429293 h
2.31217371 h
14 km
2.02895008 h
56 km
0.72297993 h
关于这道题应该要用到Dijkstra算法或者Moore-Bellman-Ford 算法？希望可以给个详细点的代码，谢谢！
学到的算法如下代码
void dijkstra_set (int s, int n) {
fill (d, d + n + 1, INF ) ;
d[s] = 0;
set <pair <int , int > > dst ;
dst . insert ({d[s], s}) ;
while (! dst. empty () ) {
int v = dst . begin () -> second ;
dst . erase ( dst . begin () );
for ( auto e: edges [v])
if (d[v] + e. cost < d[e.u]) {
dst . erase ({d[e.u], e.u}) ;
d[e.u] = d[v] + e. cost ;
dst . insert ({d[e.u], e.u}) ;
}
}
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 100;
struct Edge{
int next;
int to;
int len;
int speed;
}edge[MAXN];
int cnt;
int head[MAXN];
void Add_Edge(int u, int v, int speed, int len){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].speed = speed;
edge[cnt].len = len;
head[u] = cnt++;
}
int dis[MAXN];
struct st{
int id;
int dis;
bool operator < (const st &B)const{
return dis > B.dis;
}
};
int vis[MAXN];
const int INF = 0x3f3f3f3f;
void dijkstra(int s){
dis[s] = 0;
priority_queue<st> q;
q.push(st{s, dis[s]});
while(!q.empty()){
auto u = q.top();
q.pop();
if(vis[u.id]) continue;
vis[u.id] = 1;
for(int i=head[u.id];~i;i=edge[i].next){
int v = edge[i].to;
if(!vis[v] && dis[u.id] + edge[i].len < dis[v]){
dis[v] = dis[u.id] + edge[i].len;
q.push(st{v, dis[v]});
}
}
}
}
const double eps = 1e-10;
int dcmp(double x){
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct st2{
int id;
double t;
bool operator < (const st2 &B)const{
return dcmp(t - B.t) > 0;
}
};
double dis2[MAXN];
const double INF2 = 999999999.0;
void dijkstra2(int s){
dis2[s] = 0.0;
priority_queue<st2> q;
q.push(st2{s, dis2[s]});
while(!q.empty()){
auto u = q.top();
q.pop();
if(vis[u.id]) continue;
vis[u.id] = 1;
for(int i=head[u.id];~i;i=edge[i].next){
int v = edge[i].to;
if(!vis[v] && dcmp(dis2[v] - dis2[u.id] - edge[i].len * 1.0 / edge[i].speed) > 0){
dis2[v] = dis2[u.id] + edge[i].len * 1.0 / edge[i].speed;
q.push(st2{v, dis2[v]});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
memset(head, -1, sizeof head);
memset(dis, 0x3f, sizeof dis);
for(int i=0;i<m;i++){
int u, v, speed, len;
cin >> u >> v >> speed >> len;
Add_Edge(u, v, speed, len);
Add_Edge(v, u, speed, len);
}
int q;
dijkstra(1);
memset(vis, 0, sizeof vis);
for(int i=0;i<=n;i++) dis2[i] = INF2;
dijkstra2(1);
cin >> q;
while(q--){
int j;
char c;
cin >> j >> c;
if(c == 's'){
if(dis[j] == INF) cout << "IMPOSSIBLE\n";
else cout << dis[j] << ' ' << "km\n";
}else{
if(dcmp(dis2[j] - INF2) == 0) cout << "IMPOSSIBLE\n";
else cout << fixed << setprecision(8) << dis2[j] << ' ' << "h\n";
}
}
return 0;
}
看不太懂，看不出如果是一道图论题，那么图的节点和矩应该如何用数据结构标记？连通性和最短矩是图论的标准根算，速度有关问题是讨论了键强度的泛生问题。实际的图论解答中，键强度是优势考量因素，赋权比速度解优先。
是否为一道数组题？可以考虑一下以下数组：
//{7,11,14,17,18,19};
//{22,24,26,27,28,29};
//{51,55,56,57,58,59};
//{60,62,66,67,68,69};
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 100;
struct Edge{
int next;
int to;
int len;
int speed;
}edge[MAXN];
int cnt;
int head[MAXN];
void Add_Edge(int u, int v, int speed, int len){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].speed = speed;
edge[cnt].len = len;
head[u] = cnt++;
}
int dis[MAXN];
struct st{
int id;
int dis;
bool operator < (const st &B)const{
return dis > B.dis;
}
};
int vis[MAXN];
const int INF = 0x3f3f3f3f;
void dijkstra(int s){
dis[s] = 0;
priority_queue<st> q;
q.push(st{s, dis[s]});
while(!q.empty()){
auto u = q.top();
q.pop();
if(vis[u.id]) continue;
vis[u.id] = 1;
for(int i=head[u.id];~i;i=edge[i].next){
int v = edge[i].to;
if(!vis[v] && dis[u.id] + edge[i].len < dis[v]){
dis[v] = dis[u.id] + edge[i].len;
q.push(st{v, dis[v]});
}
}
}
}
const double eps = 1e-10;
int dcmp(double x){
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct st2{
int id;
double t;
bool operator < (const st2 &B)const{
return dcmp(t - B.t) > 0;
}
};
double dis2[MAXN];
const double INF2 = 999999999.0;
void dijkstra2(int s){
dis2[s] = 0.0;
priority_queue<st2> q;
q.push(st2{s, dis2[s]});
while(!q.empty()){
auto u = q.top();
q.pop();
if(vis[u.id]) continue;
vis[u.id] = 1;
for(int i=head[u.id];~i;i=edge[i].next){
int v = edge[i].to;
if(!vis[v] && dcmp(dis2[v] - dis2[u.id] - edge[i].len * 1.0 / edge[i].speed) > 0){
dis2[v] = dis2[u.id] + edge[i].len * 1.0 / edge[i].speed;
q.push(st2{v, dis2[v]});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
memset(head, -1, sizeof head);
memset(dis, 0x3f, sizeof dis);
for(int i=0;i<m;i++){
int u, v, speed, len;
cin >> u >> v >> speed >> len;
Add_Edge(u, v, speed, len);
Add_Edge(v, u, speed, len);
}
int q;
dijkstra(1);
memset(vis, 0, sizeof vis);
for(int i=0;i<=n;i++) dis2[i] = INF2;
dijkstra2(1);
cin >> q;
while(q--){
int j;
char c;
cin >> j >> c;
if(c == 's'){
if(dis[j] == INF) cout << "IMPOSSIBLE\n";
else cout << dis[j] << ' ' << "km\n";
}else{
if(dcmp(dis2[j] - INF2) == 0) cout << "IMPOSSIBLE\n";
else cout << fixed << setprecision(8) << dis2[j] << ' ' << "h\n";
}
}
return 0;
}