dxtsp.txt

单向的TSP旅行商问题的动态规划算法

#include<stdio.h>
#include<stdlib.h>

struct list;

typedef struct list * plist;
struct list
{
	int m;
	int n;
	int a[100][100];
	int b[100][100];
	int c[100];
	int min;
	plist link;
};

void main()
{	int i,j,x,t;
	plist p,q,head;
	scanf("%d",&x);
	p=(plist)malloc(sizeof(struct list));
	p->link=NULL;
	head=p;
	for(t=0;t<x;t++)
	{	
		scanf("%d",&p->m);
		scanf("%d",&p->n);
		for(i=0;i<p->m;i++)
			for(j=0;j<p->n;j++)
				scanf("%d",&p->a[i][j]);
        	printf("\n");
		for(i=0;i<p->n;i++)
			p->b[i][p->n-1]=p->a[i][p->n-1];
		q=(plist)malloc(sizeof(struct list));
		q->link=NULL;
		p->link=q;
		p=q;
	}
	p=head;
	while(p->link!=NULL)
	{	for(i=p->n-2;i>=0;i--)
			for(j=0;j<p->m;j++)
			{	if(j==0)
				{	if(p->b[p->m-1][i+1]<p->b[j][i+1])
						if(p->b[p->m-1][i+1]<p->b[j+1][i+1])
							p->b[j][i]=p->a[j][i]+p->b[p->m-1][i+1];
						else 
							p->b[j][i]=p->a[j][i]+p->b[j+1][i+1];
					else 
						if(p->b[j][i+1]<p->b[j+1][i+1])
							p->b[j][i]=p->a[j][i]+p->b[j][i+1];
						else
							p->b[j][i]=p->a[j][i]+p->b[j+1][i+1];
				}
				if(j==p->m-1)
				{
					if(p->b[j-1][i+1]<p->b[j][i+1])
						if(p->b[j-1][i+1]<p->b[0][i+1])
							p->b[j][i]=p->a[j][i]+p->b[j-1][i+1];
						else 
							p->b[j][i]=p->a[j][i]+p->b[0][i+1];
					else 
						if(p->b[j][i+1]<p->b[0][i+1])
								p->b[j][i]=p->a[j][i]+p->b[j][i+1];
							else
								p->b[j][i]=p->a[j][i]+p->b[0][i+1];
				}
				if(j!=0 && j!=p->m-1)
				{	if(p->b[j-1][i+1]<p->b[j][i+1])
						if(p->b[j-1][i+1]<p->b[j+1][i+1])
							p->b[j][i]=p->a[j][i]+p->b[j-1][i+1];
						else 
							p->b[j][i]=p->a[j][i]+p->b[j+1][i+1];
					else 
						if(p->b[j][i+1]<p->b[j+1][i+1])
							p->b[j][i]=p->a[j][i]+p->b[j][i+1];
						else
							p->b[j][i]=p->a[j][i]+p->b[j+1][i+1];
				}
			}
			p=p->link;
	}
	p=head;
	while(p->link!=NULL)
	{	p->min=p->b[0][0];
		for(i=1;i<p->m;i++)
			if(p->b[i][0]<p->min)
				p->min=p->b[i][0];
		printf("%d\n",p->min);
		p=p->link;
	}
}