1285.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
void floyd(vector<vector<int> > & g){
	int i,j,m,n=g.size(),newlen;
	for(m=0;m<n;m++)
	   for(i=0;i<n;i++)
		   for(j=0;j<n;j++){
			   newlen=g[i][m]+g[m][j];
			   if(newlen<g[i][j])
				   g[i][j]=newlen;
		   }
}
int main(){
    //ifstream cin("in.txt");
	int i,j,k,n,l,a,b,c,m;
	string s1,s2;
	cin>>n;
	cout<<"SHIPPING ROUTES OUTPUT\n";
	for(l=0;l<n;l++){
       cout<<"\nDATA SET "<<l+1<<"\n\n";
	   cin>>a>>b>>c;
	   vector<string> vecs(a);
	   vector<int> temptemp(a,10000);vector<vector<int> > vec(a,temptemp);
	   for(i=0;i<a;i++) cin>>vecs[i];
	   for(i=0;i<b;i++){
          cin>>s1>>s2;
		  j=find(vecs.begin(),vecs.end(),s1)-vecs.begin();
		  k=find(vecs.begin(),vecs.end(),s2)-vecs.begin();
		  vec[j][k]=vec[k][j]=1;
	   }
	   for(i=0;i<a;i++) vec[i][i]=0;
	   floyd(vec);
/*	   for(i=0;i<a;i++){
		   for(j=0;j<a;j++)
			   cout<<vec[i][j]<<" ";
		   cout<<endl;
	   }*/
	   for(i=0;i<c;i++){
           cin>>m>>s1>>s2;
		  // cout<<s1<<s2<<endl;
		   j=find(vecs.begin(),vecs.end(),s1)-vecs.begin();
		   k=find(vecs.begin(),vecs.end(),s2)-vecs.begin();
		  // cout<<m<<" "<<j<<" "<<k<<endl;
           if(vec[j][k]==10000) cout<<"NO SHIPMENT POSSIBLE\n";
           else cout<<"$"<<m*100*vec[j][k]<<endl;
	   }
	}
	cout<<"\nEND OF OUTPUT\n";
}