最短路径.cpp

里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等

#include <iostream>
using namespace std ;
#define N 10 
int cost[N] ;
int next[N] ;
 

void Print(int n)
{
	for(int i = 0 ; i < n ; i = next[i])
		cout << i + 1 << "->";
	
    cout << endl;
}


int save(int n,int i,int number[N][N] )
{
    if(i == n-1) return 0 ;
	else if(cost[i] ==0)
	{
		int temp ;
		cost[i] = 9999;
		for(int j = i+1 ; j < n ; j ++)
		{
		   if(number[i][j]!=99)
		   {
		      temp =  number[i][j] + save(n,j,number) ;
		      if(cost[i] > temp ) 
			  {
			     cost[i] = temp;
		         next[i] = j ; 
			  }
		   }
		  
		}
	}
	return cost[i] ;
}


int main()
{
	int n,i,j,number[N][N] ; ;
	
	freopen("in.txt","r",stdin) ;
	cin>>n ; cout<<n<<endl;
	for(  i = 0 ; i < n ; i ++)
	{
		for( j = 0 ; j < n ; j ++)
		{
			cin>>number[i][j];
	    	cout<<number[i][j]<< "  " ;
		}
		cout<<endl;
	}
	for( i = 0 ; i < n ; i ++)
		cost[i] = 0;
	cout<<"最短路径 ："<<save(n, 0,number)<<endl ;
	Print(n);
	return 1;
}