- 153 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 18:28:11 ]
- >>147
入力の仕様がわからなかったので，以下の仕様に従うことにした．標準入力から読み込む．
「1行目: 都市の数，2行目から: 都市1 都市2 その間の距離，終端: EOF」
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1 << 30;
// brute force using recursion ( O(n!) )
int solve(int pos, int start, vector< vector<int> >& adj, vector<bool>& used) {
used[pos] = true;
int d = inf;
if (find(used.begin(), used.end(), false) == used.end()) d = adj[pos][start];
for (int i = 0; i < used.size(); ++i)
if (!used[i]) d = min(d, adj[pos][i] + solve(i, start, adj, used));
used[pos] = false;
return d;
}
int main() {
int n; cin >> n;
vector< vector<int> > adj(n, vector<int>(n, inf));
int a, b, d;
while (cin >> a >> b >> d) adj[a][b] = adj[b][a] = d;
vector<bool> used(n, false);
int start = 0; used[start] = true;
cout << solve(start, start, adj, used) << endl;
}
|
 |
