企业网站seo,apple开发者中心,前端页面设计流程,哈尔滨房地产网站建设2596 售货员的难题 时间限制: 1 s空间限制: 32000 KB题目等级 : 钻石 Diamond题解题目描述 Description某乡有n个村庄(1n#xff1d;15)#xff0c;有一个售货员#xff0c;他要到各个村庄去售货#xff0c;各村庄之间的路程s(0s1000)是已知的#xff0c;… 2596 售货员的难题 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond 题解 题目描述 Description 某乡有n个村庄(1n15)有一个售货员他要到各个村庄去售货各村庄之间的路程s(0s1000)是已知的且A村到B村与B村到A村的路大多不同。为了提高效率他从商店出发到每个村庄一次然后返回商店所在的村假设商店所在的村庄为1他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 输入描述 Input Description 村庄数n和各村之间的路程(均是整数) 输出描述 Output Description 最短的路程 样例输入 Sample Input 3 0 2 1 1 0 2 2 1 0 样例输出 Sample Output 3 数据范围及提示 Data Size Hint 本题可用最短路思想、搜索来解决但是可能无法通过一组极限数据且效率较低。建议按树状DP考虑 分类标签 Tags 点此展开 动态规划 最小生成树 图论 AC代码1 /*不会什么树形DP我做的是spfa其实floyed就可以深搜剪枝首先将边反向spfa处理所有点到1的距离以备剪枝使用然后深搜得到答案剪枝利用spfa得到的距离当当前的dis(n-t)*minnf[x]ans时剪枝minn是矩阵中的最短距离n-t是还有几步可以遍历完所有的村庄
*/
#includecstring
#includecstdio
#includeiostream
#includequeue
#define M 20
#define INF 3000000
using namespace std;
int map[M][M],f[M],n,ansINF,min1INF;
int a2[M][M];
bool vis[M];
queueint q;
int read()
{char cgetchar();int num0,flag1;while(c0||c9){if(c-)flag-1;cgetchar();}while(c0c9){numnum*10c-0;cgetchar();}return num*flag;
}
void dfs(int x,int t,int dis)
{if(disans)return;if(dis(n-t)*min1f[x]ans)return;if(tn){ansmin(ans,dismap[x][1]);return;}for(int i1;in;i)if(!vis[i]){vis[i]true;dfs(i,t1,dismap[x][i]);vis[i]false;}
}
void spfa()
{q.push(1);vis[1]1;f[1]0;while(!q.empty()){int xq.front();q.pop();vis[x]0;for(int i1;in;i)if(a2[x][i]f[x]a2[x][i]f[i]){f[i]f[x]a2[x][i];if(!vis[i]){vis[i]1;q.push(i);}}}
}
int main()
{memset(f,0x3f3f3f3f,sizeof(f));nread();for(int i1;in;i)for(int j1;jn;j){map[i][j]read();a2[j][i]map[i][j];min1min(min1,map[i][j]);}spfa();memset(vis,0,sizeof(vis));vis[1]1;dfs(1,1,0);printf(%d,ans);return 0;
} AC代码2 #includecstdio
#includecstring
using namespace std;
#define N 51
int n,tr[N][N],m0x7fffffff;
bool vis[N];
void run(int p,int d,int s){ int r; if(dn){if(str[p][1]m) mstr[p][1];return; } for(r1;rn;r){ if(!vis[r]tr[p][r]0){ if(str[p][r]m) break; vis[r]1;run(r,d1,str[p][r]); vis[r]0;} }
}
int main(){scanf(%d,n); for(int i1;in;i) for(int j1;jn;j) scanf(%d,tr[i][j]);vis[1]1;run(1,1,0);printf(%d,m);return 0;
} AC代码3 #includeiostream
#includecstdio
#includecstring
using namespace std;
int f[20],map[16*16][16*16];
int n,a,b,c,sum0x7f7f7f7f;
void Dfs(int s ,int dis,int k)
{f[s]1;if((dis(n-k))sum) return;if(kn) {summin(sum,dismap[s][1]);}for(int i1;in;i){if(f[i]0) {Dfs(i,dismap[s][i],k1);f[i]0;}}
}
int main()
{cinn;memset(f,0,sizeof f ); for(int i1;in;i)for(int j1;jn;j)scanf(%d,map[i][j]);Dfs(1,0,1); printf(%d,sum); return 0;
} 转载于:https://www.cnblogs.com/shenben/p/5758893.html
