c 做网站源码实例,企业网站制作的公司,通辽网站建设tlyltd,网站优化升级速度限制 洛谷链接 题目大意#xff1a; 在一个城市中#xff0c;每条道路有限速和长度#xff0c;通过一条道路的时间为这条道路的长度除以限制的速度#xff0c;有的道路不知道限速为多少#xff0c;那么就按现在的速度走这条路#xff0c;找出从第一个点到目标点的最短…速度限制 洛谷链接 题目大意 在一个城市中每条道路有限速和长度通过一条道路的时间为这条道路的长度除以限制的速度有的道路不知道限速为多少那么就按现在的速度走这条路找出从第一个点到目标点的最短时间输出从起点到终点所经过的点。 解题思路 一看这道题不就是最短路径的题来spfa。但很明显单纯的spfa很难实现所以我们可以搞出一个二维数组dis[i][j]来计算速度为j时到第i个城市需要花费多少时间不断用spfa来维护这个数组。并且用两个二维数组pre1[i][j]pre2[i][j]来保存路径意思是速度为j时更新了第i个点的第pre1[i][j]个点并且该点速度为pre2[i][j]。 代码 1 #includequeue2 #includecstdio3 #includecstring4 #define M 4200005 #define N 4206 using namespace std;7 struct hehe{8 int x;9 int y;
10 hehe(){};
11 hehe(int xx,int yy){
12 xxx;
13 yyy;
14 }
15 };
16 queueheheq;
17 double dis[N][521];
18 int next[M],to[M],v[M],l[M],head[N],num,exist[N][521],pre1[N][521],pre2[N][521],n,m,p;
19 void add(int false_from,int false_to,int false_v,int false_l){
20 next[num]head[false_from];
21 to[num]false_to;
22 v[num]false_v;
23 l[num]false_l;
24 head[false_from]num;
25 }
26 void spfa(){
27 memset(dis,66,sizeof dis);
28 q.push(hehe(1,70));
29 exist[1][70]1;
30 dis[1][70]0;
31 while(!q.empty()){
32 hehe uq.front();
33 q.pop();
34 exist[u.x][u.y]0;
35 for(int ihead[u.x];i;inext[i]){
36 if(!v[i]){
37 if(1.0*l[i]/u.ydis[u.x][u.y]dis[to[i]][u.y]){
38 dis[to[i]][u.y]1.0*l[i]/u.ydis[u.x][u.y];
39 pre1[to[i]][u.y]u.x;
40 pre2[to[i]][u.y]u.y;
41 if(!exist[to[i]][u.y]){
42 exist[to[i]][u.y]1;
43 q.push(hehe(to[i],u.y));
44 }
45 }
46 }
47 else{
48 if(1.0*l[i]/v[i]dis[u.x][u.y]dis[to[i]][v[i]]){
49 dis[to[i]][v[i]]1.0*l[i]/v[i]dis[u.x][u.y];
50 pre1[to[i]][v[i]]u.x;
51 pre2[to[i]][v[i]]u.y;
52 if(!exist[to[i]][v[i]]){
53 exist[to[i]][v[i]]1;
54 q.push(hehe(to[i],v[i]));
55 }
56 }
57 }
58 }
59 }
60 }
61 void print(int a,int b){
62 if(a!1)
63 print(pre1[a][b],pre2[a][b]);
64 printf(%d ,a-1);
65 }
66 int main(){
67 scanf(%d%d%d,n,m,p);
68 p;
69 for(int i1;im;i){
70 int a,b,c,d;
71 scanf(%d%d%d%d,a,b,c,d);
72 add(a1,b1,c,d);
73 }
74 spfa();
75 double mmin1e30;
76 int minn0;
77 for(int i1;i500;i)
78 if(mmindis[p][i]){
79 mmindis[p][i];
80 minni;
81 }
82 print(pre1[p][minn],pre2[p][minn]);
83 printf(%d\n,p-1);
84 return 0;
85 } View Code 转载于:https://www.cnblogs.com/jsawz/p/6835865.html
