菜單導航

cls200(200分求解C 10個城市最短路徑問題!!

迪傑斯特拉算法 你百度一下或者找本C語言版的數據結構裏面圖納章節裏就有這個算法的詳細課程和原理

這個是 求一個無重複最小環的問題# include <cstdio># include <cstring># include <cstdlib># include <iostream># include <fstream>const int MAXN = 500;const int MAX = 0x3ffffff;using namespace std;int vis[MAXN],path[MAXN],ans[MAXN];int n,mat[MAXN][MAXN],MIN = MAX;void dfs(int start, int len, int tot) // start 起始點 len 目前爲止的距離 tot 已經加入的邊數{ if (tot == n-1) { if (len < MIN) { for(int i = 0; i < n; i) ans[i] = path[i]; MIN = len; } } else { for(int i = 1; i <= n; i) { if (start == i || mat[start][i] == MAX) continue; if (vis[i]) continue; //可行性剪紙 if (MIN < len mat[start][i]) continue;// 最優化剪紙 path[tot 1] = i; vis[i] = 1; dfs(i,len mat[start][i],tot 1); path[tot 1] = 0; vis[i] = 0; } }}int main(){ freopen("input1.txt","r",stdin); int m[MAXN][MAXN]; int suffix[MAXN][MAXN]; cin >> n; for(int i = 1 ; i <= n; i) for(int j = 1; j <= n; j) { cin >> m[i][j] ; if (m[i][j] == -1) m[i][j] = MAX; suffix[i][j] = j; mat[i][j] = m[i][j]; } fclose(stdin); freopen("CON","r",stdin); for(int k = 1 ; k <= n; k) for(int i = 1 ; i <= n; i) for(int j = 1; j <= n; j) { //int len = ; if (m[i][j] > m[i][k] m[k][j]) { m[i][j] = m[i][k] m[k][j]; suffix[i][j] = suffix[i][k]; } }cout << "\t有" << n << "個景點的校園導遊程序。。。\n\n"; cout << "\t按1 查詢任意兩個“景點”的最短路\n"; cout << "\t按2 給出遍曆全部景點的最短時間\n\t";int op ; char ch; cin >> op; if (op == 1) { do {int u,v; cout << "\t景點1cls200:" ; cin >> u; cout << "\t景點2:" ; cin >> v; if (u < 0 || u > n || u < 0 || u > n ) { cout << "輸入錯誤" << endl; return 0; } cout << "\n\n\t從景點" << u << "到景點" << v << "最短路徑長度爲" << m[u][v] ; cout << "\n\t路徑如下 : \n\t景點" << u ; while( u != v) { cout << " -> 景點" << suffix[u][v]; u = suffix[u][v]; } cout << "\n\t繼續?(y/n)"; cin >> ch; } while(ch == 'y') ; } else if (op == 2) { for(int i = 1; i <= n; i) { memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); vis[i] = 1; path[0] = i; dfs(i,0,0);} cout << "\t遍曆全圖 所花費的最短時間是:" << MIN ; cout << "\n\t路徑如下:\n\t" << ans[0] ; for(int i = 1; i < n; i) cout << " -> " << ans[i]; } return 0;}