loadingif(inq[i]==0&&minlen>mp[u][i])/*取与所有点的连边中最小的边*/ {
minlen=mp[u][i]; p=i; } }
inq[p]=1;
return dfs(p,k+1,l+minlen); }
int get_lb(node p) {
int ret=p.sumv*2;//路径上的点的距离
int min1=INF,min2=INF;//起点和终点连出来的边 for(int i=1; i<=n; i++) {
if(p.visp[i]==0&&min1>mp[i][p.st]) {
min1=mp[i][p.st]; } }
ret+=min1;
for(int i=1; i<=n; i++) {
if(p.visp[i]==0&&min2>mp[p.ed][i]) {
min2=mp[p.ed][i]; } }
ret+=min2;
for(int i=1; i<=n; i++) {
if(p.visp[i]==0) {
min1=min2=INF; for(int j=1; j<=n; j++) {
if(min1>mp[i][j]) min1=mp[i][j]; }
for(int j=1; j<=n; j++) {
if(min2>mp[j][i]) min2=mp[j][i]; }
ret+=min1+min2; } }
return ret%2==0?(ret/2):(ret/2+1); }
void get_up() {
inq[1]=1; up=dfs(1,1,0); }
void get_low() {
low=0;
for(int i=1; i<=n; i++) {
/*通过排序求两个最小值*/ int min1=INF,min2=INF; int tmpA[22];
for(int j=1; j<=n; j++) {
tmpA[j]=mp[i][j]; }
sort(tmpA+1,tmpA+1+n);//对临时的数组进行排序 low+=tmpA[1]; } }
int solve() {
/*贪心法确定上界*/ get_up();
/*取每行最小的边之和作为下界*/ get_low();
/*设置初始点,默认从1开始 */ node star; star.st=1; star.ed=1; star.k=1;
for(int i=1; i<=n; i++) star.visp[i]=0; star.visp[1]=1; star.sumv=0; star.lb=low;
/*ret为问题的解*/ int ret=INF;
q.push(star);
while(!q.empty()) {
node tmp=q.top(); q.pop();
if(tmp.k==n-1) {
/*找最后一个没有走的点*/ int p;
for(int i=1; i<=n; i++) {
if(tmp.visp[i]==0) {
p=i; break; } }
int ans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p]; node judge = q.top();
/*如果当前的路径和比所有的目标函数值都小则跳出*/ if(ans <= judge.lb) {
ret=min(ans,ret); break; }
/*否则继续求其他可能的路径和，并更新上界*/ else {
up = min(up,ans); ret=min(ret,ans); continue; } }
/*当前点可以向下扩展的点入优先级队列*/ node next;
for(int i=1; i<=n; i++) {
if(tmp.visp[i]==0) {
next.st=tmp.st;
/*更新路径和*/
next.sumv=tmp.sumv+mp[tmp.ed][i];
/*更新最后一个点*/ next.ed=i;
/*更新顶点数*/ next.k=tmp.k+1;
/*更新经过的顶点*/
for(int j=1; j<=n; j++) next.visp[j]=tmp.visp[j]; next.visp[i]=1;
/*求目标函数*/ next.lb=get_lb(next);
/*如果大于上界就不加入队列*/ if(next.lb>up) continue; q.push(next); } } }
return ret; }
int main() {
in();
printf(\ return 0; }
四、运行输出结果：
（贴出程序运行完成时的屏幕截图或者输出文件的内容） 这里采用相同的两组数据进行测试。 1、动态规划法
样例1：