解题思路:
注意事项:
参考代码:
#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 人评分
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1607 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1099 |
A+B for Input-Output Practice (C语言代码)浏览:468 |
大家好,我是验题君浏览:577 |
交换Easy (C语言代码)浏览:763 |
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:1038 |
1162答案错误,为什么浏览:644 |
C二级辅导-计负均正 (C语言代码)浏览:643 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:485 |
C语言程序设计教程(第三版)课后习题8.3 (C++代码)浏览:508 |