> 不就是单原点最短路径吗？？
> 
> #include <vector>
> #include <deque>
> #include <list>
> #include <set>
> #include <map>
> #include <string>
> #include <stack>
> #include <numeric>
> #include <algorithm>
> #include <functional>
> #include <iterator>
> #include <cmath>
> #include <complex>
> #include <limits>
> #include <iostream>
> #include <sstream>
> #include <fstream>
> using namespace std;
> 
> #define BE(a) (a).begin(),(a).end()
> #define FOR(i,j,k) for(i=j; i<k; ++i)
> #define REP(i,n) FOR(i, 0, n)
> 
> 
> typedef pair<int, int> PII;
> typedef vector<int> VI;
> typedef vector<VI> VII;
> typedef vector<string> VS;
> 
> 
> int F,P,C,M;
> vector<vector<double> > costMatrix;
> vector<bool> used;
> vector<double> result;
> vector<int> pos;
> const double INF = 1e20;
> int main(){
> 	ifstream fileget("1.txt");
> 	fileget >> F >> P >> C >> M;
> 	costMatrix.assign(F+1, vector<double>(F+1, INF));
> 	used.assign(F+1, false);
> 	result.assign(F+1, INF);
> 	int i,j;
> 	for(i=1; i<F+1; ++i)
> 		costMatrix[i][i] = 0;
> 	pos.assign(C+1);
> 	while(P--){
> 		int f1,f2,c;
> 		fileget >> f1 >> f2 >> c;
> 		costMatrix[f1][f2] = costMatrix[f2][f1] = c;
> 	}
> 	int index = 1;
> 	while(C--){
> 		int i;
> 		fileget >> i;
> 		pos[index++] = i;
> 	}
> 	/*
> 	FOR(i, 1, F+1){
> 		FOR(j,1,F+1)
> 			cout << costMatrix[i][j] << " ";
> 		cout << endl;
> 	}
> 	*/
> 	int cnt = 1;	
> 	result[1] = 0;
> 	while(cnt != F){
> 		double m = INF;
> 		int index;
> 		FOR(i,1,F+1)
> 			if (!used[i] && result[i] < m){
> 				m = result[i];
> 				index = i;
> 			}
> 		used[index] = true;
> 		FOR(i, 1, F+1)
> 			if (costMatrix[1][index]+costMatrix[index][i]<result[i])
> 				result[i] = costMatrix[1][index]+costMatrix[index][i];
> 			
> 		++cnt;
> 	}
> 
> 	/*
> 	copy(result.begin()+1, result.end(), ostream_iterator<int>(cout, " "));
> 	cout << endl;
> 	copy(pos.begin()+1, pos.end(), ostream_iterator<int>(cout, " "));
> 	cout << endl;
> 	*/
> 	int ret = 0;
> 	vector<int> ans;
> 	FOR(i,1,pos.size()){
> 		//pos[i]:牛i在pos[i]节点
> 		if (result[pos[i]] <= M){
> 			++ret;
> 			ans.push_back(i);
> 			/*
> 			cout << result[pos[i]] << endl;
> 			cout << i << endl;
> 			cout << pos[i] << endl;
> 			*/
> 		}
> 	}
> 	cout << ret << endl;
> 	copy(BE(ans), ostream_iterator<int>(cout, "\n"));
> 	return 1;
> }

• Re:为什么wa啊？ (2215) yangguo981 2006-05-19 01:30:33