Gym100624F CERC2012 Farm and Factory 最短路、切比雪夫距离

传送门

---

设(f_i)表示(i)到(1)号点的最短距离，(g_i)表示(i)到(2)号点的最短距离，(s_i)表示(n+1)号点到(i)号点的最短距离，(A=s_1,B=s_2)

根据最短路三角形不等式，(|f_i - A| leq s_i leq f_i + A , |g_i - B| leq s_i leq g_i + B)

而(s_i)要取到最小值，所以(s_i = max{|f_i - A| , |g_i - B|})

所以我们要求的是(sumlimits_{i=1}^N max{|f_i - A| , |g_i - B|})，这相当于求一个动点((A,B))到平面上(N)个点((f_i,g_i))的最小切比雪夫距离和。

切比雪夫距离可以转为曼哈顿距离，将坐标((x,y))变为((frac{x+y}{2} , frac{x-y}{2}))，前者的切比雪夫距离等效于后者的曼哈顿距离。而曼哈顿距离可以直接拆开横纵坐标然后取中位数。

注意：我天真的以为2012年的题不会卡SPFA……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;

inline int read(){
	int a = 0;
	char c = getchar();
	while(!isdigit(c) && c != EOF)
		c = getchar();
	while(isdigit(c)){
		a = a * 10 + c - 48;
		c = getchar();
	}
	return a;
}

#define PLI pair < long long , int >
#define st first
#define nd second
const int MAXN = 1e5 + 7;
struct Edge{
	int end , upEd , w;
}Ed[MAXN * 6];
int head[MAXN] , N , M , cntEd;
long long dis[2][MAXN];
priority_queue < PLI > q;

inline void addEd(int a , int b , int w){
	Ed[++cntEd].end = b;
	Ed[cntEd].w = w;
	Ed[cntEd].upEd = head[a];
	head[a] = cntEd;
}

void SPFA(int ind){
	memset(dis[ind] , 0x3f , sizeof(long long) * (N + 1));
	dis[ind][ind + 1] = 0;
	q.push(PLI(0 , ind + 1));
	while(!q.empty()){
		PLI t = q.top();
		q.pop();
		if(-t.st != dis[ind][t.nd]) continue;
		for(int i = head[t.nd] ; i ; i = Ed[i].upEd)
			if(dis[ind][Ed[i].end] > dis[ind][t.nd] + Ed[i].w){
				dis[ind][Ed[i].end] = dis[ind][t.nd] + Ed[i].w;
				q.push(PLI(-dis[ind][Ed[i].end] , Ed[i].end));
			}
	}
}

inline long long abss(long long x){return x < 0 ? -x : x;}

void out(long long a , int b){
	cout << a / b << '.';
	a %= b;
	for(int i = 1 ; i <= 8 ; ++i){
		a *= 10;
		cout << a / b;
		a %= b;
	}
	putchar('
');
}

int main(){
	vector < long long > x , y;
	for(int T = read() ; T ; --T){
		N = read(); M = read();
		memset(head , 0 , sizeof(int) * (N + 1));
		cntEd = 0;
		for(int i = 1 ; i <= M ; ++i){
			int a = read() , b = read() , c = read();
			addEd(a , b , c); addEd(b , a , c);
		}
		SPFA(0); SPFA(1);
		x.clear(); y.clear();
		long long sum = 0;
		for(int i = 1 ; i <= N ; ++i){
			x.push_back(dis[0][i] - dis[1][i]);
			y.push_back(dis[0][i] + dis[1][i]);
		}
		sort(x.begin() , x.end()); sort(y.begin() , y.end());
		long long mid = x[N >> 1];
		for(int i = 0 ; i < N ; ++i)
			sum += abss(x[i] - mid);
		mid = y[N >> 1];
		for(int i = 0 ; i < N ; ++i)
			sum += abss(y[i] - mid);
		out(sum , 2 * N);
		cerr << N << ' ' << sum << endl;
	}
	return 0;
}