1333.cpp

来自「ZOJ 动态规划算法题目入门与提高 源代码」· C++ 代码 · 共 55 行

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
#include<cmath>
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;
		   }
}
void makemap(vector<vector<int> > & map,vector<char> & name,vector<string> & path){
	int k;
	for(int i=0;i<map.size();i++){
		for(int j=0;j<path[i].length();j++){
           k=find(name.begin(),name.end(),path[i][j])-name.begin();
		   map[i][k]=map[k][i]=1;
		}
	}
}
int main(){
    //ifstream cin("in.txt");
	string s,r;
	int i,j,k,n;
	while(getline(cin,s)){
        istringstream ns(s);
		ns>>n;
		vector<char> vecname(n+1); vector<double> val(n+1); vector<string> path(n+1,"");
		vecname[0]='*'; val[0]=0;
		for(i=1;i<=n;i++){
           getline(cin,s);
		   istringstream is(s);
		   is>>vecname[i]>>val[i]>>path[i];
		}
		vector<int> _map(n+1,100000);
		vector<vector<int> > map(n+1,_map);
		makemap(map,vecname,path);
		floyd(map);
		for(i=0;i<n+1;i++){
           if(map[0][i]>=1000) val[i]=0;
		   else{
               val[i]*=pow(0.95,map[0][i]-1);
		   }
		}
		k=max_element(val.begin(),val.end())-val.begin();
		cout<<"Import from "<<vecname[k]<<endl;
	}
}