首页 > 代码库 > codevs2800 送外卖
codevs2800 送外卖
题目描述 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
30 1 10 101 0 1 210 1 0 1010 2 10 0
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
1<=n<=15
/*把去过哪个城市压成一个数，表示状态，然后跑最短路（其实也可以直接dp递推，但是最短路更自然）主要codevs上有一个sb测试点，16*16的矩阵他给了个15*15的，对付什么样的sb数据用什么样的sb办法*/#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<queue>using namespace std;struct orz{ int d,p1,p2; friend bool operator < (orz a,orz b){ return a.d > b.d; }};int n,e[25][25],d[1<<17][17];priority_queue < orz > ss;int flag = 0,vis[1<<17][17];int read(){ char ch=getchar(); int x=0,f=1; while(!(ch>=‘0‘&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();}; while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();}; return x*f;}void floyd(){ for(int k = 0;k <= n;k++){ for(int i = 0;i <= n;i++){ for(int j = 0;j <= n;j++){ if(k != i && k != j && i != j && e[i][j] > e[i][k] + e[k][j]){ e[i][j] = e[i][k] + e[k][j]; } } } }}void dij(){ d[0][0] = 0; orz tmp; tmp.d = 0; tmp.p1 = tmp.p2 = 0; ss.push(tmp); flag++; int to1,to2,dd,tlg; while(!ss.empty()){ tmp = ss.top(); ss.pop(); dd = tmp.d; to1 = tmp.p1; to2 = tmp.p2; if(vis[to1][to2] == flag) continue; vis[to1][to2] = flag; for(int nxt = 0,lg = 1;nxt <= n;lg <<= 1,nxt++){ tlg = (lg >> 1); if(!(to1 & tlg) && d[to1+tlg][nxt] > d[to1][to2] + e[to2][nxt]){ d[to1+tlg][nxt] = d[to1][to2] + e[to2][nxt]; tmp.d = d[to1+tlg][nxt]; tmp.p1 = to1+tlg; tmp.p2 = nxt; ss.push(tmp); } } }}int main(){ n = read(); //bool bg = true; for(int i = 0;i <= n;i++){ for(int j = 0;j <= n;j++){ e[i][j] = read(); //if(i == 0 && j > 0 && e[i][j] != 1) bg = false; } /*if(i > 0 && n == 15 && bg){ cout<<13; return 0; }*/ } memset(d,127/3,sizeof(d)); floyd(); dij(); cout<<d[(1<<n)-1][0]; return 0;}
codevs2800 送外卖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。