[Aha]城市地图

2019-11-06 06:05:27

字体：大中小

来源：转载

供稿：网友

题目：详见啊哈算法P136页，就是城市间的最简单的城市最短路问题。

分析：DFS跑一下即可。

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std ;int e[5000][5000];int n ;int book[5000];int min_n ; void dfs(int cur , int dis){ if(dis>min_n) return ; if(cur == 5){ if(dis<min_n) min_n = dis ; return ; } for(int i = 1; i <= n ; i++){ if(book[i]==0&&e[cur][i]!=999999&&e[cur][i]!=0){ book[i] = 1 ; dfs(i,dis+e[cur][i]); book[i] = 0 ; } } return ; }int main(){ freopen("in.txt","r",stdin); int m ,a, b ,dis; while(scanf("%d %d",&n,&m)!=EOF){ min_n = 999999; for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= m ; j++){ if(i==j) e[i][j] = 0 ; else e[i][j] = 999999 ; } } memset(book,0,sizeof(book)); for(int i = 1 ; i <= m ; i++){ scanf("%d %d %d",&a,&b,&dis); e[a][b] = dis ; } book[1] = 1 ; dfs(1,0); PRintf("%d/n",min_n); } return 0 ;}

上一篇：中国（北方）大学生程序设计训练赛（第一周）(Problem E: Water Problem-矩阵快速幂)

下一篇：C语言练习1