hdu 1596 find the safest road(最短路径，邻接矩阵)

本文主要是介绍hdu 1596 find the safest road(最短路径，邻接矩阵)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：http://acm.hdu.edu.cn/showproblem.php?pid=1596

考验图论中的最短路径问题。需要做一点小小的处理，把原算法中的if(dist[j]>dist[k]+map[k][j])dist[j]=dist[k]+map[k][j];改成if(dist[j]<dist[k]*map[k][j])dist[j]=dist[k]*map[k][j];其他就没啥了。

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,i,j;
const int maxn=1005;
double map[maxn][maxn],dis[maxn],pre[maxn];
void Dijkstra(int s){bool tag[maxn];double mmax;int k;memset(tag,0,sizeof(tag));memset(dis,0,sizeof(dis));tag[s]=1;for(i=1;i<=n;i++){dis[i]=map[s][i];}for(i=1;i<n;i++){mmax=0;k=0;for(j=1;j<=n;j++){if(mmax<dis[j]&&!tag[j]&&dis[j]>0){k=j;mmax=dis[j];}}if(!k)return ;tag[k]=1;for(j=1;j<=n;j++){if(!tag[j]&&(dis[j]<map[k][j]*dis[k])){dis[j]=map[k][j]*dis[k];}}}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n){for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%lf\n",&map[i][j]);}}int q;scanf("%d",&q);for(int ix=0;ix<q;ix++){int a,b;scanf("%d%d",&a,&b);Dijkstra(a);double ans=dis[b];if(ans<1e-6)printf("What a pity!\n");else  printf("%.3lf\n",ans);}}return 0;
}

写的过程中，曾出现过一个神奇的现象，原来的主函数中第二个for循环是这样的：

for(i=0;i<q;i++){int a,b;scanf("%d%d",&a,&b);Dijkstra(a);double ans=dis[b];if(ans<1e-6)printf("What a pity!\n");else  printf("%.3lf\n",ans);}

结果每次没有输入q次a,b就跳出了循环，我下了身冷汗~原来是全局变量搞的鬼，调用Dijkstra函数后i的值被改变了。

这篇关于hdu 1596 find the safest road(最短路径，邻接矩阵)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---