lanqiao oj 1050 补给

简介: lanqiao oj 1050 补给

用户登录

先用floyd求出最短路,然后用状态压缩dp求出

状态压缩dp和坐标搜寻差不多

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std ;
const int N = 20 ;
double INF = 1e9;
 
double f[1<<N][N] ;
double w[N][N] ;
int n ;
double d ; 
double x[N] , y[N] ;
double dis(int a,int b ){
    return sqrt((x[a] - x[b])*(x[a] - x[b]) + ((y[a] - y[b]) *(y[a] - y[b] ))) ;
}
 
void floyd(){
    for(int k = 0 ; k < n ; k ++){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0; j < n ; j ++){
                w[i][j] = min(w[i][j] , w[i][k] + w[k][j]) ;
            }
        }
    }
}
int main(){
    cin >> n >> d ;
    for(int i = 0 ; i < n ; i++){
        cin >> x[i] >> y[i] ;
    }
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ;j ++){
            w[i][j] = w[j][i] = dis(i,j) ;
            if(w[i][j] > d) w[i][j] = w[j][i] = INF ;
        }
    }
    floyd() ;
    memset(f,127,sizeof(f)) ;
    f[1][0] = 0 ;
    for(int s = 0 ; s < 1 << n ; s ++){
        for(int i = 0 ; i < n ; i ++){
            if(((s >> i) & 1))
            for(int j = 0 ; j < n ; j ++){
                if((s ^(1<<i)) >> j & 1){
                    f[s][i] = min(f[s][i], f[s ^(1<<i)][j] + w[j][i]) ;
                }
            }
        }
    }
    double res = INF;
    for(int i = 1 ; i < n ;i ++) {
        res = min (f[(1<<n)-1][i] + w[i][0], res ) ;
    }
    printf("%.2f",res);
}
目录
相关文章
|
2月前
lanqiao OJ 1030 蓝肽子序列
lanqiao OJ 1030 蓝肽子序列
38 2
|
2月前
lanqiao OJ 1388 寒假作业
lanqiao OJ 1388 寒假作业
33 0
|
2月前
lanqiao OJ 689 四阶幻方
lanqiao OJ 689 四阶幻方
27 0
|
2月前
lanqiao OJ 389 摆花
lanqiao OJ 389 摆花
17 2
|
2月前
lanqiao OJ 364 跳石头
lanqiao OJ 364 跳石头
34 6
|
2月前
lanqiao OJ 649 算式900
lanqiao OJ 649 算式900
15 1
|
2月前
lanqiao OJ 525 传球游戏
lanqiao OJ 525 传球游戏
28 2
|
2月前
lanqiao OJ 108 发现环
lanqiao OJ 108 发现环
14 1
|
2月前
lanqiao oj Frog
lanqiao oj Frog
23 0
|
2月前
lanqiao oj 1085 小猪存钱罐
lanqiao oj 1085 小猪存钱罐
28 0