题目：P1027 [NOIP2001 提高组] Car 的旅行路线

问题:第四个测试点过不去（后附）

代码（c++）如下：

#include<cstdio>
#include<queue>
#include<cmath>
#define for(i,n) for(int i = 1;i <= n;i++)

struct point{
	int x,y,citybelongt;
}P[500];

int n,s,t,a,b,cst[200];
int cnt;
double dis[500],ans;
std::queue<int> q;

void find_another_side(int city,int ct)
{
	if(((P[ct].x - P[ct+1].x)*(P[ct+1].x - P[ct+2].x) == (P[ct+1].y - P[ct].y)*(P[ct+1].y - P[ct+2].y)))
	{
//		printf("f");  中间是直角 
		P[++cnt].x = P[ct].x + P[ct+2].x - P[ct+1].x;
		P[cnt].y = P[ct].y + P[ct+2].y - P[ct+1].y;
		P[cnt].citybelongt = city;
		return ;
	}
	else if(((P[ct+1].x - P[ct+2].x)*(P[ct+2].x - P[ct].x) == (P[ct+2].y - P[ct+1].y)*(P[ct+2].y - P[ct].y)))
	{
//		printf("s"); 第三个为直角 
		P[++cnt].x = P[ct].x + P[ct+1].x - P[ct+2].x;
		P[cnt].y = P[ct].y + P[ct+1].y - P[ct+2].y;
		P[cnt].citybelongt = city;
		return ;
	}
	else
	{
//		printf("t%d %d %d %d %d %d\n",P[ct].x,P[ct+1].x,P[ct+2].x,P[ct].y,P[ct+1].y,P[ct+2].y);//3 7 4 2 9 3  第一个为直角 
		P[++cnt].x = P[ct+2].x + P[ct+1].x - P[ct].x;
		P[cnt].y = P[ct+2].y + P[ct+1].y - P[ct].y;
		P[cnt].citybelongt = city;
		return ;
	}
}

void read(int city)
{
	for(i,3)
		++cnt,
		scanf("%d%d",&P[cnt].x,&P[cnt].y),
		P[cnt].citybelongt = city;
	find_another_side(city,cnt - 2);
}

double dst(int u,int v)
{
	return sqrt((P[u].x - P[v].x)*(P[u].x - P[v].x) + (P[u].y - P[v].y)*(P[u].y - P[v].y));
}

void spfa()
{
	double cost;
	bool vis[1000] = {false};
	for(i,cnt) dis[i] = 99999999.99;
	for(i,4) dis[4*a-4+i] = 0,q.push(4*a-4+i),vis[4*a-4+i] = true;
//	for(i,cnt) printf("%f\n",dis[i]);
	while(!q.empty())
	{
//		printf("f%f %f %f %ff\n",dis[cnt],dis[cnt-1],dis[cnt-2],dis[cnt-3]);
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(i,cnt)
		{
			cost = dst(i,u);
			if(i == u) continue;
			else if(P[i].citybelongt == P[u].citybelongt) cost *= cst[P[i].citybelongt];
			else cost *= t;
//			printf("iu%d %d %f %f %f\n",i,u,dis[i],dis[u],cost);
			if(dis[i] > dis[u] + cost)
			{
				dis[i] = dis[u] + cost;
				if(!vis[i])
					vis[i] = true,
					q.push(i);
			}
		}
	}
}

int main()
{
	scanf("%d",&n);
	loop:
		ans = 99999999.99;
		cnt = 0;
		scanf("%d%d%d%d",&s,&t,&a,&b);
		for(i,s)
			read(i),
			scanf("%d",&cst[i]);
//		printf("%d",cnt);
		spfa();
		for(i,4)
//			printf("%d %f\n",i,dis[cnt-i+1]),
			ans = ans > dis[cnt-i+1] ? dis[cnt-i+1] : ans;
		printf("%.1f",ans);
		n--;
	if(n) goto loop;
	return 0;
} 

测试点数据:

1

10 10 1 2

27 27 194 105 194 27 10

366 290 381 290 366 305 10

80 158 196 245 196 158 1

289 154 358 154 358 86 2

17 284 84 350 84 284 1

175 289 292 289 175 362 3

450 371 420 371 420 32 2

241 29 270 29 270 43 4

251 182 347 270 251 270 5

347 341 410 341 347 369 1

参考答案:

1885.0

本人答案：

2073.1

蒟蒻求助，忘大佬帮助，帮帮孩子吧...