codevs2800送外卖(状压dp)

author author     2022-09-24     776

关键词:

题目描述 Description

有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市可以走多次),最后还要回到0点(他的单位),请问最短时间是多少。现在已知任意两个城市的直接通路的时间。

输入描述 Input Description

第一行一个正整数n (1<=n<=15)

接下来是一个(n+1)*(n+1)的矩阵,矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同,也就是说道路都是单向的。

输出描述 Output Description

一个正整数表示最少花费的时间

样例输入 Sample Input

 

 

样例输出 Sample Output

8

数据范围及提示 Data Size & Hint

1<=n<=15

题解::

先用floyed求出每两个点的距离。

用f[i][j]表示在第i个城市,状态为j的最小代价,

方程:f[i][j]=min(f[i][j],min(f[k][j],f[k][j^(1<<i)])+a[k][i]);k为每个城市。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<0||ch>9)f|=(ch==-),ch=getchar();
    while(ch>=0&&ch<=9)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
    return;
}
int a[20][20],f[20][1<<18];
int main()
{
    int n;
    read(n);
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    scanf("%d",&a[i][j]);
    for(int k=0;k<=n;k++)
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    int t=(1<<n+1)-1;
    memset(f,0x7f,sizeof(f));
    f[0][0]=0;
    for(int k=0;k<=t;k++)
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    {
        if((k|(1<<i))!=k)continue;
        f[i][k]=min(f[i][k],min(f[j][k],f[j][k^(1<<i)])+a[j][i]);
    }
    printf("%d
",f[0][t]);
    return 0;
}

 

codevs2800送外卖

【算法】最短路(floyd)&&状态压缩型动态规划(DP)【题解】dp的顺序应该是由含1的个数少的二进制到1的个数高的二进制(第一重循环)#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintinf=0x3f3f3f3f,maxn=18;intm 查看详情

「codevs」2800送外卖(代码片段)

题意:原题在这快递小哥从city0出发去(n+1)*(n+1)城市矩阵中送快递,求来回最短时间 做法:TSP问题,这里选用dp做法Floyd初始化城市间的距离;令dp[1<<i][i]=dis[0][i]; 表示先走一格,好转移dp[s][j]表示走了j个城市,状态为... 查看详情

状压dp

2800送外卖 时间限制:2s 空间限制:256000KB 题目等级:钻石Diamond题解 查看运行结果 题目描述 Description有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在... 查看详情

[codevs2800]送外卖

[codevs2800]送外卖试题描述有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市可以走多次)... 查看详情

codevs2800送外卖

题目描述 Description有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市可以走多次),... 查看详情

[codevs2800]送外卖

题目描述 Description有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市可以走多次),... 查看详情

codevs2800送外卖

题目描述 Description有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市可以走多次),... 查看详情

状压dp送餐员

[odevs2800]送餐员题目描述 Description有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次(一个城市... 查看详情

「美团codem初赛roundb」送外卖2---------------状压dp(代码片段)

题目描述一张 n 个点 m 条有向边的图上,有 q  个配送需求,需求的描述形式为 (si,ti,li,ri)(s_i,t_i,l_i,r_i)(si?,ti?,li?,ri?),即需要从点 si 送到 ti,在时刻 li 之后(包括 lil_ili?&nbs 查看详情

区间dp-送外卖

Whenwearefocusingonsolvingproblems,weusuallyprefertostayinfrontofcomputersratherthangooutforlunch.Atthistime,wemaycallforfooddelivery.Supposethereare N peoplelivinginastraightstreetthatisjus 查看详情

codevs1358棋盘游戏(状压dp)

1358棋盘游戏  时间限制:1s 空间限制:64000KB 题目等级:大师Master  题目描述 Description这个游戏在一个有10*10个格子的棋盘上进行,初始时棋子位于左上角,终点为右下角,棋盘上每个格子内有一个0到9的数... 查看详情

codevs2594解药还是毒药(状压dp)

2594解药还是毒药  时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond  题目描述 DescriptionSmart研制出对付各种症状的解药,可是他一个不小心,每种药都小小地配错了一点原料,所以这些药都有可能在治... 查看详情

codevs2596售货员的难题(状压dp)

2596售货员的难题  时间限制:1s 空间限制:32000KB 题目等级:钻石Diamond  题目描述 Description某乡有n个村庄(1<n<=15),有一个售货员,他要到各个村庄去售货,各村庄之间的路程s(0<s<1000)是已知的,且... 查看详情

[codevs1050]棋盘染色2(状态压缩dp)

...这题是插头DP,结果今天一看发现不用>_<,虽然还是状压DP。   因为只有5列,所以 查看详情

程序人生干了三年程序员,我决定兼职送外卖

 目  录为什么去送外卖送外卖经历过程送外卖收入状况一些趣事的分享停止送外卖原因送外卖心得感受 写在最后为什么去送外卖当时我的手机只有64GB,但实在太多东西不想清理掉,就想换个最新款的小米手机,256... 查看详情

codevs1344线型网络

Sol随机化算法+哈密顿路径.好厉害的题...首先都会想到状压DP对吧,复杂度(O(n^22^n)).(n=20)  exm??(10^8)有一种算法就是随机化算法再调整.通过随机化算法,再(O(n^2))来调整.调整方式如下:如果有(dis(i-1,i)+dis(j,j+1)>dis(i-1,j)+dis(i,j+1)... 查看详情

状压dp小结

1.要状压的那一维,所有有关的下标要从0开始,而不是从1开始2.预处理很重要,可以说基本所有的状压dp都要有预处理这玩意 查看详情

hoj2662经典状压dp//myfirst状压dp

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言:用dp解决一个问题的时候很重要的一环就是状态的表示,一般来说,一个数组即可保存状态。但是有这样的一类题目,它们具有dp问题的特性,但状态中所包含的信息过多,... 查看详情