1456.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<string>
#include<sstream>
#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const string jian="-->";  int f,t,n,j,i,m,l,k;
bool small(vector<int> & a,vector<int> & b){
	int ii;
	if(a.size()>=b.size()){
        for(ii=0;ii<b.size();ii++){
           if(a[ii]<b[ii]) return true;
		   if(a[ii]>b[ii]) return false;
		}
		return false;
	}
	else{
        for(ii=0;ii<b.size();ii++){
           if(a[ii]<b[ii]) return true;
		   if(a[ii]>b[ii]) return false;
		}
		return true;
	}
}
int main(){

  while(cin>>n&&n){
     vector<int> vectemp(n),vecvectemp;
	 vector<vector<int> > stringtemp(n);
	 vector<vector<vector<int> > > vecs(n,stringtemp);
	 vector<vector<int> > vec(n,vectemp);
	 vector<int> cost(n);
	 for(k=0;k<n;k++)
		 for(l=0;l<n;l++){
			 cin>>vec[k][l];
             vecs[k][l].clear();
			 if(k==l) vecs[k][l].push_back(k+1);
			 else{vecs[k][l].push_back(k+1);vecs[k][l].push_back(l+1);}
		 }
	 for(k=0;k<n;k++) cin>>cost[k];
	 for(m=0;m<n;m++)
		 for(i=0;i<n;i++)
			 for(j=0;j<n;j++){
                 if(vec[i][m]!=-1&&vec[m][j]!=-1){
					 if(vec[i][j]==-1||vec[i][j]>vec[i][m]+vec[m][j]+cost[m]){
                         vec[i][j]=vec[i][m]+vec[m][j]+cost[m];
						 vecs[i][j]=vecs[i][m];
						 for(k=1;k<vecs[m][j].size();k++)
							 vecs[i][j].push_back(vecs[m][j][k]);
					 }
					 else if(vec[i][j]==vec[i][m]+vec[m][j]+cost[m]){
						 vector<int> temptemp=vecs[i][m];
						 for(k=1;k<vecs[m][j].size();k++)
							 temptemp.push_back(vecs[m][j][k]);
						 if(small(temptemp,vecs[i][j])) vecs[i][j]=temptemp;
					 }
				 }
			 }
	 while(cin>>f>>t&&f!=-1){
		 cout<<"From "<<f<<" to "<<t<<" :\n";
         cout<<"Path: ";
		 for(i=0;i<vecs[f-1][t-1].size();i++){
            if(i!=0) cout<<jian;
			cout<<vecs[f-1][t-1][i];
		 }
		 cout<<endl;
         cout<<"Total cost : "<<vec[f-1][t-1]<<endl<<endl;
	 }
  }
}