#include <iostream>
#include <cmath>
using namespace std;

struct Point{
	int x, y;
};

int const MAX = 500;
double adj[MAX][MAX];
Point vetex[MAX];
int n = 2; //the number of vetex
double EP = 1e-10;

int index(Point p){
	for(int i = 0; i < n ; i++)
		if(p.x == vetex[i].x && p.y == vetex[i].y)
			return i;
	vetex[n].x = p.x;
	vetex[n++].y = p.y;
}

double pointDistance(Point p1, Point p2){
	double d = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
	return sqrt(d);
}

int main(){
	cin>>vetex[0].x>>vetex[0].y>>vetex[1].x>>vetex[1].y;
	Point pre, next;
	while(cin>>pre.x>>pre.y){
		int indexPre = index(pre);
		int indexNext;
		while(cin>>next.x>>next.y && !(next.x == -1 && next.y == -1)){
			indexNext = index(next);
			adj[indexPre][indexNext] = adj[indexNext][indexPre] = pointDistance(vetex[indexPre], next);
			indexPre = indexNext;
		}
	}

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(abs(adj[i][j]) < EP)
				adj[i][j] = 4 * pointDistance(vetex[i], vetex[j]);

	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(adj[i][k] + adj[k][j] < adj[i][j])
					adj[i][j] = adj[i][k] + adj[k][j];

	double d = adj[0][1] * 6 / 4000 ;
	int n = d;
	if(d - n > 0.5)
		cout<<n+1<<endl;
	else 
		cout<<n;
    return 0;
}

• Re:为什么runtime error，我用最短路（暂用floyed，原想超时后改用迪杰斯特拉）可是。。 (20) chengmingvictor 2005-07-29 18:23:34