请问做网站需要什么软件,响应式购物网站模板,网络设计解决方案,微信公号嵌入网站开发一道最短路问题。普通最短路问题的边只有一种权值#xff0c;而此题的边要考虑两种权值。因为节点n1000#xff0c;所以不能够使用Floyd算法#xff0c;时间复杂度较高#xff0c;这里使用Dijkstra算法解决。 中文描述#xff0c;题意不再赘述。只是要注意每条边都有距… 一道最短路问题。普通最短路问题的边只有一种权值而此题的边要考虑两种权值。因为节点n1000所以不能够使用Floyd算法时间复杂度较高这里使用Dijkstra算法解决。 中文描述题意不再赘述。只是要注意每条边都有距离和花费两种权当且仅当两条边的距离相等时才比较花费。因为需要考虑两种权所以算法代码要有相应的改变。另外要考虑重边的问题依旧要考虑两种权值。 下面是解题代码Dijkstra解法 1 #include stdio.h2 #define N 10013 #define INF 99999994 5 int map[N][N]; /*距离图*/6 int cost[N][N]; /*花费图*/7 int dis[N]; /*起点到i的距离*/8 int cos[N]; /*起点到i的花费*/9 int flag[N]; /*标志变量*/10 int n, m;11 int s, t;12 13 void Init(); /*初始化*/14 15 void Read(); /*输入*/16 17 void Dijkstra();18 19 int main()20 {21 while (~scanf(%d %d, n, m))22 {23 if (n 0 m 0)24 {25 break;26 }27 Init();28 Read();29 Dijkstra();30 printf(%d %d\n, dis[t], cos[t]);31 }32 return 0;33 }34 35 void Init() /*初始化*/36 {37 int i, j;38 for (i1; in; i)39 {40 for (j1; jn; j)41 {42 map[i][j] cost[i][j] INF;43 }44 dis[i] cos[i] INF;45 flag[i] 0;46 }47 return;48 }49 50 void Read() /*输入*/51 {52 int i;53 int a, b, c, d;54 for (i0; im; i)55 {56 scanf(%d %d %d %d, a, b, c, d);57 if (map[a][b] c || (map[a][b] c cost[a][b] d)) /*解决重边*/58 {59 map[a][b] map[b][a] c;60 cost[a][b] cost[b][a] d;61 }62 }63 scanf(%d %d, s, t);64 return;65 }66 67 void Dijkstra()68 {69 int i, j, k;70 int mind, minc;71 dis[s] cos[s] 0;72 for (i1; in; i)73 {74 mind minc INF;75 for (j1; jn; j)76 {77 /*多权值的比较*/78 if (flag[j] 0 (mind dis[j] || (mind dis[j] minc cos[j])))79 {80 mind dis[k j];81 minc cos[k];82 }83 }84 flag[k] 1;85 for (j1; jn; j)86 {87 if (flag[j] 0 dis[j] dis[k] map[k][j])88 {89 dis[j] dis[k] map[k][j];90 cos[j] cos[k] cost[k][j];91 }92 /*当距离相同时考虑花费*/93 if (flag[j] 0 dis[j] dis[k] map[k][j] cos[j] cos[k] cost[k][j])94 {95 cos[j] cos[k] cost[k][j];96 }97 }98 }99 return;
100 } 转载于:https://www.cnblogs.com/JZQT/p/3802445.html
