hdup2544

http://acm.hdu.edu.cn/showproblem.php?pid=2544

dfs（暴力）

#include<iostream> using namespace std; int mindis = INT_MAX; int map[101][101]; int book[101]; void dfs(int cur, int dis, int n){ //剪枝 if (dis > mindis) return; //出口 if (cur == n){ if (mindis > dis){ mindis = dis; } return; } //核心算法 for (int i = 1; i <= n; i++){ if (!book[i] && map[cur][i] != INT_MAX){ book[i] = 1; dfs(i, map[cur][i] + dis, n); book[i] = 0; } } } int main(){ int n, m; int a, b, c; while (cin >> n >> m && n && m){ //两个初始化 memset(book, 0, sizeof(book)); mindis = INT_MAX; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ map[i][j] = INT_MAX; } } for (int i = 0; i < m; i++){ cin >> a >> b >> c;//输入数据 map[a][b] = c; map[b][a] = c; } book[1] = 1; dfs(1, 0, n); cout << mindis << endl; } return 0; }

Floyd

#include<iostream> using namespace std; int map[101][101]; int inf = 200000; int main(){ int n, m; int a, b, c; while (cin >> n >> m && n && m){ //初始化 for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (i == j) map[i][j] = 0; else map[i][j] = inf; } } //读入数据 for (int i = 1; i <= m; i++){ cin >> a >> b >> c; map[a][b] = c; map[b][a] = c; } //Floyd核心算法 for (int k = 1; k <= n; k++){ for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (map[i][j] > map[i][k] + map[k][j]){ map[i][j] = map[i][k] + map[k][j]; } } } } cout << map[1][n] << endl; } return 0; }

Dijkstra

#include<iostream> using namespace std; int map[101][101]; int book[101]; int dis[101]; int inf = 200000; int main(){ int n, m; int a, b, c; int u; while (cin >> n >> m && n && m){ //初始化 for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (i == j) map[i][j] = 0; else map[i][j] = inf; } } //读入数据 for (int i = 1; i <= m; i++){ cin >> a >> b >> c; map[a][b] = c; map[b][a] = c; } //初始化dis,book for (int i = 1; i <= n; i++){ dis[i] = map[1][i]; } for (int i = 1; i <= n; i++){ book[i] = 0; } book[1] = 1; //Dijkstra核心算法 for (int i = 1; i <= n - 1; i++){ int min = inf; for (int j = 1; j <= n; j++){ if (book[j]==0 && min > dis[j]){ min = dis[j]; u = j; } } book[u] = 1; for (int k = 1; k <= n; k++){ if (map[u][k]<inf){ if (dis[k] > dis[u] + map[u][k]){ dis[k] = dis[u] + map[u][k]; } } } } cout << dis[n] << endl; } return 0; }