题目链接 http://hdu.hustoj.com/showproblem.php?pid=3001
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- inline ll read(){
- int x=0,f=1;char ch=getchar();
- while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- /***********************************************************/
- int n, m; // n <= 10
- const int maxn = 6e4+5;
- int d[12][maxn];
- // 用三进制形式来表示状态
- int dist[15][15];
- // 表示路径
- int t[12];
- int cnt, state[maxn];
- int temp;
- // 判断 S 的三进制是否没有一个 0
- bool legal(int S){
- bool ok = true;
- for(int i = 0;i <= n-1;i++){
- if(S%3 == 0){
- ok = false;
- break;
- }
- S /= 3;
- }
- return ok;
- }
- void init(){
- temp = 1;
- for(int i = 0;i <= 10;i++){
- t[i] = temp;
- temp *= 3;
- }
- }
- //i 点在集合 S 中是否出现了至少一次
- inline bool in(int i, int S){
- for(int j = 0;j < i;j++)
- S /= 3;
- if(S%3) return true;
- else return false;
- }
- int dp(int i, int S){
- if(d[i][S]>= 0) return d[i][S];
- int &ans = d[i][S];
- ans = 1e9;
- int S1 = S - t[i];
- for(int j = 0;j <n;j++){
- if(j != i && in(j, S1) && dist[j][i] != -1)
- ans = min(ans, dp(j, S1) + dist[j][i]);
- }
- return ans;
- }
- int main(){
- init();
- while(~scanf("%d %d", &n, &m)){
- int max_3 = 0;
- for(int i = 0;i < n;i++)
- max_3 += t[i];
- cnt = 0;
- for(int S = max_3;S < t[n];S++){
- if(legal(S))
- state[cnt++] = S;
- }
- memset(dist, -1, sizeof(dist));
- for(int i = 0;i < m;i++){
- int a, b, c;
- scanf("%d%d%d", &a, &b, &c);
- a--;b--;
- // 更新长度
- if(dist[a][b] == -1 || dist[a][b]> c)
- dist[a][b] = dist[b][a] = c;
- }
- memset(d, -1, sizeof(d));
- for(int i = 0;i < n;i++)
- d[i][t[i]] = 0;
- int sum = dp(0, max_3);
- for(int i = 0;i < n;i++){
- for(int j = 0;j < cnt;j++){
- sum = min(sum, dp(i, state[j]));
- }
- }
- if(sum == 1e9) printf("-1\n");
- else printf("%d\n", sum);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2815594.html