求多短路的最短路径，用动态规划法.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <iostream.h>

//求多短路的最短路径，用动态规划法
/*
输入
10 18
0 1 4
0 2 2
0 3 3
1 4 9
1 5 8
2 4 6
2 5 7
2 6 8
3 5 4
3 6 7
4 7 5
4 8 6
5 7 8
5 8 6
6 7 6
6 8 5
7 9 7
8 9 3

输出
0->3->5->8->9
*/
#define INFI 1000
int c[15][15];//路径长度
int cost[15];
int path[15];//在最短路径上，每个点的后继

void search(int n)
{
	int i,j,minnum;
	for(i=0;i<n;i++)
		cost[i]=INFI;
	cost[n-1]=0;
	for(i=n-2;i>=0;i--)
	{
		for(j=n-1;j>i;j--)
		{
			if(cost[i]>c[i][j]+cost[j]) 
			{
				cost[i]=c[i][j]+cost[j];//修改当前最短路径的大小
				minnum=j;
			}
		}
		path[i]=minnum;//记下在最短路径上，该点的后继
	}
}

void print(int n,int start)
{
	int next=start;
	do
	{
		cout<<next<<"->";
		next=path[next];//求该点的后继
	}while(next!=n-1);
	cout<<next<<endl;
}
int main()
{
	int num,pnum,i,j,ta,tb,tc;
	cout<<"几个点,几条路？"<<endl;
	cin>>num>>pnum;
	for(i=0;i<num;i++)
		for(j=0;j<num;j++)
			c[i][j]=INFI;
	for(i=0;i<pnum;i++)
	{
		cin>>ta>>tb>>tc;
		c[ta][tb]=tc;
	}
	search(num);
	cout<<"点0到终点的最短路径为：";
	print(num,0);
	return 0;
}