[백준/BOJ] 백준 13141번 : Ignition

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

13141번: Ignition

어떤 정점끼리 연결되어 있는지에 대한 정보를 저장하고, 해당 정점 사이에 가장 짧은 간선의 길이와, 가장 긴 간선의 길이를 저장한 뒤, 정점끼리 가장 짧은 간선으로만 이루어진 그래프를 만들었다. 그리고 모든 정점마다 해당 정점에서 출발한 다익스트라를 통해 해당 정점에서 각 정점까지 가장 빠른 시간을 저장했고, 이를 통해 각 정점들 사이에 가장 긴 간선들을 모두 확인하며 해당 간선이 언제 삭제되는지 구했다. 그중 가장 늦게 지워지는 간선의 시간이 모든 그래프의 간선이 지워지는 시간이라는 것을 이용해서 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int n, m;
vector<pair<int, int>> adj[201]; //해당 정점 사이의 가장 짧은 간선으로만 이루어진 그래프
vector<vector<int>> edge_min(201, vector<int>(201, 987654321)); //[정점1][정점2] = 정점1과 정점2 사이의 가장 짧은 거리
vector<vector<int>> edge_max(201, vector<int>(201, -1)); //[정점1][정점2] = 정점1과 정점2 사이의 가장 긴 거리
vector<pair<int, int>> edge_info; //어떤 정점 사이의 간선이 있는지 저장

double Solve(int start)
{
	vector<int> min_cost(201, 987654321); //start에서 해당 지점까지 최단거리 저장
	priority_queue<pair<int, int>> pq;

	min_cost[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (min_cost[here] < here_cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < min_cost[there])
			{
				min_cost[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}

	double ret = 0;

	//정점 사이의 가장 긴 간선을 확인하여 해당 간선이 언제 삭제되는지 구한다
	//그중 가장 늦게 지워지는 시간이 모든 그래프의 간선이 지워지는 시간
	for (int i = 0; i < edge_info.size(); i++)
	{
		int u = edge_info[i].first;
		int v = edge_info[i].second;
		int max_len = edge_max[u][v]; //해당 간선의 길이

		int visited_time1 = min(min_cost[u], min_cost[v]); //u와 v중에 먼저 도착한 정점의 시간
		int visited_time2 = max(min_cost[u], min_cost[v]); //u와 v중에 나중에 도착한 정점의 시간

		if (visited_time2 - visited_time1 > max_len) //시간 차이가 간선의 길이보다 클때
		{
			ret = max(ret, (double)visited_time1 + (double)max_len);
		}

		else //나중에 도착한 정점도 해당 간선을 태우는데 도움이 될때
		{
			int remain_max_len = max_len - (visited_time2 - visited_time1); //먼저 도착한게 태우고 남은 길이
			ret = max(ret, (double)visited_time1 + (double)(visited_time2 - visited_time1) + ((double)remain_max_len / 2));
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int s, e, l;
		cin >> s >> e >> l;

		int u = min(s, e);
		int v = max(s, e);

		edge_info.push_back(make_pair(u, v));
		edge_max[u][v] = max(edge_max[u][v], l);
		edge_min[u][v] = min(edge_min[u][v], l);
	}

	//어떤 정점 사이의 간선이 있는지에 대한 정보 중복되는것 제거
	edge_info.erase(unique(edge_info.begin(), edge_info.end()), edge_info.end());

	//가장 짧은 간선으로만 이루어진 그래프를 만든다
	for (int i = 0; i < edge_info.size(); i++)
	{
		int u = edge_info[i].first;
		int v = edge_info[i].second;

		adj[u].push_back(make_pair(edge_min[u][v], v));
		adj[v].push_back(make_pair(edge_min[u][v], u));
	}

	double result = 987654321;
	for (int i = 1; i <= n; i++)
	{
		result = min(result, Solve(i));
	}

	cout << fixed;
	cout.precision(1);
	cout << result;

	return 0;
}