백준 15775 Voronoi Diagram

https://www.acmicpc.net/problem/15775

15775번: Voronoi Diagram

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

이번 문제에서는 다익스트라 알고리즘을 사용합니다.

 

1. 핵심 아이디어

 

첫번째, 문제를 풀기위해서는 특정 노드가 어떤 정점이랑 가장 가까운지 알아야합니다.

단순히 생각하면 K번의 다익스트라가 필요하겠지만

아래와 같은방법으로 생각하면 1번의 다익스트라만 사용하면됩니다.

 

그림을 통해서 같이 설명하겠습니다.

 

 

정점집합을 하나의 노드라고 생각하고 다익스트라를 시작합니다.

여기서 우선순위 큐에 들어갈 값을 이렇게 정의 합니다.

(이동가중치, 현재노드, 주인정점)       //주인정점 : 해당 노드에서 가장 가까운 정점

 

위의 그림을 토대로 정점 집합 1, 3 우선순위큐에 넣는다한다면

pq.push({ 0, 1, 1 });  pq.push({ 0, 3, 3 });

라는 값이 큐에 들어갑니다.

 

다익스트라를 진행하면서 주인정점을 표시해줍니다. 

 

 

다익스트라가 실행되다보면 이러한 상황에 직면하게됩니다.

 

이 경우 우선순위 큐에 정점의 값까지 포함했으므로

정점번호가 더 낮은 값으로 바꿔주면됩니다. 따로 예외처리합니다.

 

두번째, 두가지 색상으로 칠해지는 간선을 알아내야합니다.

 

위의 그래프의 주인정점을 모두 찾아주면 다음그림과 같이 나옵니다.

여기서 두가지 색상으로 칠해지는 간선은 

 

 

빨간색으로 표시한 두곳으로 

 

두가지 색상으로 표시되는 간선은 양끝노드의 주인정점이 다르다는 것을 확인 할 수 있습니다.

반대로 한가지 색상으로 표시되는 간선은 양끝노드의 주인정점이 같습니다.

 

 

 

 

 

이제 문제를 풀기위한 정보를 다 구했습니다.

모든 간선에 대하여

만약. 양끝노드의 주인정점이 값다면

Ans[주인정점] += cost;     //cost : 간선 가중치 , Ans[i] : i번 정점을 주인정점으로하는 간선들의 합

 

아니면 양끝노드의 주인정점이 다르다면

int sum = Dist[왼쪽정점] + cost+ Dist[오른쪽정점];  //Dist[i] : 정점집합으로부터 i번 노드까지의 최단거리

Ans[왼쪽 주인정점] += abs(Dist[왼쪽정점] - sum * 0.5);

Ans[오른쪽 주인정점] += abs(Dist[오른쪽정점] - sum * 0.5);

 

 

자세한건 코드를 참조해주세요.

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const int INF = 999999999999999;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
//////////////////////////////////////////////////////////////////////// 

const int MAX = 250005;
int N, M, K;
int Dist[MAX];
int Owner[MAX];
float Ans[MAX];

vector<int> a; 
vector<pair<int, int>> V[MAX];
vector<pair<pair<int, int>,int>> Edge;

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int s, e, w;
		std::cin >> s >> e >> w;
		V[s].push_back({ e,w });
		V[e].push_back({ s,w });

		Edge.push_back({ {s,e},w });
	}

	for (int i = 1; i <= N; i++)
	{
		Dist[i] = INF;
		Owner[i] = INF;
	}

	std::cin >> K;
	for (int i = 0; i < K; i++)
	{
		int k;
		std::cin >> k;
		a.push_back(k);
	}

	priority_queue<pair<int,pair<int, int>>> pq; //이동가중치, 현재노드, 주인정점
	for (int i = 0; i < a.size(); i++)
	{
		pq.push({ 0,{a[i],a[i] } });
		Dist[a[i]] = 0;
		Owner[a[i]] = a[i];
	}

	while (pq.empty() == false)
	{
		pair<int, pair<int, int>> nowQ = pq.top();
		pq.pop();

		int nowP = nowQ.second.first;
		int nowOwner = nowQ.second.second;
		int nowCost = -nowQ.first;

		if (Dist[nowP] < nowCost)
			continue;

		for (int i = 0; i < V[nowP].size(); i++)
		{
			pair<int, int> next = V[nowP][i];
			int nextP = next.first;
			int nextCost = nowCost + next.second;

			if (Dist[nextP] > nextCost)
			{
				Dist[nextP] = nextCost;
				Owner[nextP] = nowOwner;
				pq.push({ -nextCost,{nextP,nowOwner } });
			}
			else if (Dist[nextP] == nextCost && Owner[nextP] > nowOwner)
			{
				//해당 노드는 주인정점이 2개이상이다.
				//가장 작은 주인정점으로 갱신한다.
				Owner[nextP] = nowOwner;
				pq.push({ -nextCost,{nextP,nowOwner } });
			}
		}
	}

	for (int i = 0; i < Edge.size(); i++)
	{
		int s = Edge[i].first.first;
		int e = Edge[i].first.second;
		int cost = Edge[i].second;

		if (Owner[s] == Owner[e])
		{
			//양쪽 주인노드가 같다.
			Ans[Owner[s]] += cost;
		}
		else
		{
			//양쪽 주인노드가 다르다.
			float sum = Dist[s] + cost + Dist[e];
			Ans[Owner[s]] += abs(Dist[s] - sum * 0.5);
			Ans[Owner[e]] += abs(Dist[e] - sum * 0.5);
		}
	}

	//둘째자리에서 반올림후 정답 출력
	cout << fixed << setprecision(1);
	for (int i = 0; i < a.size(); i++)
	{
		cout << Ans[a[i]] << endl;
	}
}