解题思路:
注意事项:
参考代码:
#include<iostream> #include<algorithm> #define MAX 99999 using namespace std; double m[500+1][500+1]; double dis[500+1]; int S[500+1]; int n,k; void dijkstra(int star){ //初始化dis for(int i=1; i<=n; i++) dis[i]=m[star][i]; S[star]=1; for(int i=1; i<=n-1; i++){ //找出S集合外,距离原点最近的点 double mint=MAX; for(int j=1; j<=n; j++){ if(S[j]==0 && mint>dis[j]){ mint=dis[j]; star=j; } } S[star]=1; //更新dis for(int j=1; j<=n; j++) dis[j]=min(dis[j],dis[star]+m[star][j]); } } int main(){ cin>>n>>k; for(int i=1; i<=n; i++ ){ for(int j=1; j<=n; j++){ cin>>m[i][j]; if(m[i][j]==0) m[i][j]=MAX; } S[i]=0; } double v; for(int i=1; i<=n; i++ ){ for(int j=1; j<=n; j++){ cin>>v; if(v!=0) m[i][j]/=v; //权重变为时间 } } dijkstra(1); printf("%.2lf\n",dis[k]); return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:560 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:545 |
WU-输入输出格式练习 (C++代码)浏览:1082 |
最小公倍数 (C语言代码)浏览:1029 |
C二级辅导-阶乘数列 (C语言代码)浏览:522 |
交换Easy (C语言代码)浏览:763 |
简单的a+b (C语言代码)浏览:416 |
Manchester-数字整除最原始易理解方法浏览:4485 |
【亲和数】 (C++代码)浏览:534 |
Manchester- A+B for Input-Output Practice (II)浏览:1318 |