題目：詳見啊哈算法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);新聞熱點
疑難解答
