算法题之图论 [NOIP2001 提高组] Car的旅行路线详细题解

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

这道题的思路呢，就是建个图，然后跑一遍Floyd，比较最小值就可以解决了。

but!它每个城市只给三个点（共四个），所以还得计算出第四个点坐标。这里根据矩形的中点公式来表示未知点的坐标：（这个思路源于大佬  _jimmywang_

勾股定理判断一下哪两个点构成对角线，然后就能求出这个点了。（具体代码在get_forth()函数）

由于建图把所有点都放一张二维表g[i][j]，而一个城市有四个点，所以用 i,j通过除4或取余4的方案来表示第几个城市以及第几个城市的第几个点（具体代码在下面函数中）。

由于一个城市有4个点，如果单独设x,y坐标的话，感觉有点太麻烦，所以我采用了结构体的方式，记录每个城市的4个点和对应的单位行程花销。（并且用多个函数分步实现功能，逻辑比较清晰点

最后用floyd实现最小值的求取。

#include <iostream> 
#include <cmath>
#include <iomanip> 
using namespace std;
#define N 101
#define INF 999999999
struct City {
	int x[4],y[4];
	int price;
}; //把一个City的四个机场点都放一起
int s, t, A, B;
City cities[N];
double g[402][402], ans; // 邻接数组存储图，ans答案
int square(int n) {
	return n * n;
}
double pointDistance(int x1, int y1, int x2, int y2) {
	return sqrt(square(x1 - x2) + square(y1 - y2));
}
void get_forth(City& cities) {
	int ab = square(cities.x[0] - cities.x[1]) + square(cities.y[0] - cities.y[1]);
	int bc = square(cities.x[1] - cities.x[2]) + square(cities.y[1] - cities.y[2]);
	int ac = square(cities.x[0] - cities.x[2]) + square(cities.y[0] - cities.y[2]);
	if (ab + bc == ac) {
		cities.x[3] = cities.x[0] + cities.x[2] - cities.x[1];
		cities.y[3] = cities.y[0] + cities.y[2] - cities.y[1];
	}
	else if(ac + bc == ab){
		cities.x[3] = cities.x[0] + cities.x[1] - cities.x[2];
		cities.y[3] = cities.y[0] + cities.y[1] - cities.y[2];
	}
	else {
		cities.x[3] = cities.x[1] + cities.x[2] - cities.x[0];
		cities.y[3] = cities.y[1] + cities.y[2] - cities.y[0];
	}
}
void init_graph(int s) {
	for (int i = 1; i <= s; i++) {
		for (int j = 1; j <= s; j++) {
			if (i != j) {
				g[i][j] = INF;
			}
			else {
				g[i][j] = 0;
			}
		}
	}
	ans = INF;
	return ;
}
//求最短路 Floyd
//建图 需要一个比较大的二维数组来存储各边之间的长短
//此时已经记录了各个点之间的花销
void build_graph(int s,int t) {
	for (int i = 1; i <= s; i++) {
		for (int j = 1; j <= s; j++) {
			if (g[i][j] == INF) {
				int m1=i/4, n1=j/4;
				if (i % 4 != 0) {
					m1 += 1;
				}
				if (j % 4 != 0) {
					n1 += 1;
				}

				g[i][j] = t * sqrt(square(cities[m1].x[(i-1)%4] - cities[n1].x[(j-1)%4]) + square(cities[m1].y[(i - 1) % 4] - cities[n1].y[(j - 1) % 4]));
				g[j][i] = g[i][j];
			}
		}
	}
}
void inits(int s) {
	for (int i = 1; i <= s; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> cities[i].x[j] >> cities[i].y[j];
		}
		cin >> cities[i].price;
		//第四个点需要计算出来
		get_forth(cities[i]);
		for (int n1 = 1; n1 <= 4; n1++) {
			for (int n2 = 1; n2 <= 4; n2++) {
				if(n1!=n2)
					g[4 * (i-1)+n1][4 * (i - 1) + n2] = cities[i].price * sqrt(square(cities[i].x[n1-1] - cities[i].x[n2-1]) + square(cities[i].y[n1-1] - cities[i].y[n2-1]));
			}
		}//计算四个点内的花销
		/*for (int ss = 0; ss < 4; ss++) {
			cout << cities[i].x[ss] <<"  "<< cities[i].y[ss] << endl;
		}*/
	}
	/*for (int i = 1; i <= 4 * s; i++) {
		for (int j = 1; j <= 4 * s; j++) {
			cout << setw(10) << g[i][j];
		}
		cout << endl;
	}
	cout << endl;
	*/
	return;
}
//利用Floyd算法进行最小化
double Floyd(int cnt,int A,int B){
	for (int k = 1; k <= cnt; k++)
		for (int i = 1; i <= cnt; i++)
			for (int j = 1; j <= cnt; j++)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
	double mins = INF;
	int n, m;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			mins = min(mins, g[4 * (A-1) + i][j + 4 * (B-1)]);
			//cout << g[4 * (A - 1) + i][j + 4 * (B - 1)] << " ";
		}
		//cout << endl;
	}
	return mins;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		cin >> s >> t >> A >> B;
		init_graph(4 * s);
		inits(s); //初始化所有的飞机场坐标信息+建图
		build_graph(4 * s, t);
		
		/*for (int i = 1; i <= 4 * s; i++) {
			for (int j = 1; j <= 4 * s; j++) {
				cout << setw(10)<<g[i][j];
			}
			cout << endl;
		}*/
		cout <<fixed << setprecision(1) << Floyd(s * 4, A, B)<<endl;//setprecision(1)<<
	}
	return 0;
}

 美美（终于）过了