不就是单原点最短路径吗？？

#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啊？ (2387) yangguo981 2006-05-19 01:18:14
  • Re:为什么wa啊？ (2215) yangguo981 2006-05-19 01:30:33