fcm.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

struct disj{
	int pa[2000005];
	void init(int n){
		for(int i=0; i<=n; i++) pa[i] = i;
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

struct edg{
	int pos, idx, cst;
};

int n, m;
int xp[50005], yp[50005];
vector<edg> gph[50005];
int s[1000005], e[1000005], x[1000005];
int access[2000005], vis[2000005];

int gcol[2000005]; // color of each vertice
vector<pi> gph2[1000005];

struct fin{
	int pos, used, cst;
	bool operator>(const fin &f)const{
		return cst > f.cst;
	}
};

priority_queue<fin, vector<fin>, greater<fin> > pq;
bool myvis[1000005][2];

int dijkstra(int s, int e){
	pq.push({s, 0, 0});
	while(!pq.empty()){
		auto x = pq.top();
		pq.pop();
		if(x.pos == e) return x.cst;
		if(myvis[x.pos][x.used]) continue;
		myvis[x.pos][x.used] = 1;
		for(auto &i : gph2[x.pos]){
			pq.push({i.second, x.used, x.cst + i.first});
			if(x.used == 0){
				pq.push({i.second, 1, x.cst});
			}
		}
	}
	assert(0);
}

int solve1(){
	int ret = 0, col = 0;
	for(int i=0; i<m; i++){
		ret += x[i];
	}
	for(int i=0; i<2*m; i++){
		if(disj.find(i) == i){
			col++;
			gcol[i] = col;
		}
	}
	for(int i=0; i<2*m; i++){
		if(disj.find(i) != i){
			gcol[i] = gcol[disj.find(i)];
		}
	}
	col++;
	for(int i=0; i<2*m; i++){
		if(vis[i] == -1){
			gcol[i] = col;
		}
	}
	int st = gcol[gph[1].back().idx^1];
	int ed = col;
	for(int i=0; i<2*m; i+=2){
		gph2[gcol[i]].push_back({x[i/2], gcol[i+1]});
		gph2[gcol[i+1]].push_back({x[i/2], gcol[i]});
	}
	return ret - dijkstra(st, ed);
}

void dfs2(int edg, int c){
	vis[edg] = c;
	int pos = access[edg^1]+1;
	int ep = (edg % 2 == 0 ? e[edg/2] : s[edg/2]);
	if(ep == n) return;
	if(pos >= gph[ep].size()) pos = 0;
	dfs2(gph[ep][pos].idx, c);
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d %d",&xp[i],&yp[i]);
	}
	scanf("%d",&m);
	for(int i=0; i<m; i++){
		scanf("%d %d %d",&s[i],&e[i],&x[i]);
		gph[s[i]].push_back({e[i], 2*i, x[i]});
		gph[e[i]].push_back({s[i], 2*i+1, x[i]});
	}
	disj.init(2*m);
	for(int i=1; i<=n; i++){
		sort(gph[i].begin(), gph[i].end(), [&](const edg &a, const edg &b){
			int dx1 = xp[a.pos] - xp[i];
			int dy1 = yp[a.pos] - yp[i];
			int dx2 = xp[b.pos] - xp[i];
			int dy2 = yp[b.pos] - yp[i];
			return atan2(dy1, dx1) < atan2(dy2, dx2);
		});
		for(int j=0; j<gph[i].size(); j++){
			auto nxt = gph[i][(j+1)%gph[i].size()];
			disj.uni(gph[i][j].idx^1, nxt.idx);
			access[gph[i][j].idx] = j;
		}
	}
	dfs2(gph[1][0].idx, -1);
	int ret = solve1();
	priority_queue<pi, vector<pi>, greater<pi> > pq;
	pq.push(pi(0, 1));
	bool vis[50005] = {};
	while(!pq.empty()){
		auto x = pq.top();
		pq.pop();
		if(vis[x.second]) continue;
		vis[x.second] = 1;
		if(x.second == n){
			printf("%d %d\n", x.first, ret);
			return 0;
		}
		for(auto &i : gph[x.second]){
			pq.push(pi(i.cst + x.first, i.pos));
		}
	}
}