我是靠谱客的博主 清脆小鸽子,这篇文章主要介绍最短路径问题【浙江大学复试上机题】【最短路径】,现在分享给大家,希望可以做个参考。

题目描述

给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。

输入描述:

复制代码
1
2
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)

输出描述:

复制代码
1
输出 一行有两个数, 最短距离及其花费。

示例1

输入

复制

复制代码
1
2
3
4
5
3 2 1 2 5 6 2 3 4 5 1 3 0 0

输出

复制

复制代码
1
9 11

套模板,根据题意“若最短距离有多条路径,则输出花费最少的”,修改松弛的操作。

如果距离减小,重新赋值距离

如果距离不变,看花费是否减小,若是,重新复制花费 

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream> #include<vector> #include<queue> #include<climits> #include<cstring> using namespace std; const int MAXN=1001; const int INF=INT_MAX; struct Point{ int number; int distance; Point(int n,int l):number(n),distance(l){} bool operator < (Point x)const{ return distance > x.distance; } }; struct Edge{ int to; int len; int co; Edge(int t,int l,int c):to(t),len(l),co(c){} }; vector<Edge> graph[MAXN]; int dis[MAXN]; int cost[MAXN]; void Init(int n){ fill(dis,dis+n+1,INF); fill(cost,cost+n+1,INF); memset(graph,0,sizeof(graph)); } void Dijkstra(int s){ dis[s]=0; cost[s]=0; priority_queue<Point> q; q.push(Point(s,0)); while(!q.empty()){ int u=q.top().number; q.pop(); for(int i=0;i<graph[u].size();i++){ int v=graph[u][i].to; int len=graph[u][i].len; int co=graph[u][i].co; if(dis[v]>dis[u]+len){ //松弛 dis[v]=dis[u]+len; cost[v]=cost[u]+co; q.push(Point(v,dis[v])); } else if(dis[v]==dis[u]+len){ if(cost[v]>cost[u]+co){ cost[v]=cost[u]+co; q.push(Point(v,dis[v])); } } } } } int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ Init(n); if(n==0&&m==0){ break; } for(int i=0;i<m;i++){ int from,to,len,co; scanf("%d%d%d%d",&from,&to,&len,&co); graph[from].push_back(Edge(to,len,co)); graph[to].push_back(Edge(from,len,co)); } int s,t; scanf("%d%d",&s,&t); Dijkstra(s); printf("%d %dn",dis[t],cost[t]); } return 0; }

 

最后

以上就是清脆小鸽子最近收集整理的关于最短路径问题【浙江大学复试上机题】【最短路径】的全部内容,更多相关最短路径问题【浙江大学复试上机题】【最短路径】内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(53)

评论列表共有 0 条评论

立即
投稿
返回
顶部