[BAE/<JOON> 문제풀이] 13141. Ignition

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

13141번: Ignition

핵심::
간선 별로 다 태우는 시간을 구하는 공식을 생각해보면 된다.

풀이::
플로이드 알고리즘으로 모든 정점에 불이 도착하는 가장 빠른 시간을 n3 시간에 구할 수 있다.

간선의 양 끝 정점에 불이 도착하는 가장 빠른 시간을 a, b라고 하고 간선의 길이를 e라고 하면 간선이 다 타는 시간은 

(e - abs(a - b) / 2) + max(a + b) 이다.

정점이 200개에 간선이 20000개로 제한되어있고 구하는 식이 다항식이므로 그냥 다 해보면 된다.

최대 입력 크기 데이터에서 정점마다 모두 시도해도 연산 횟수는 4000000회 밖에 안된다.

의견::
플레티넘 난이도가 아님. 솔직히 정말로

 

코드::

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

#define pragma once
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma pack(1)

using namespace std;

struct edge {
	int s, d, v;
};

int main()
{
	int n, m; cin >> n >> m;
	vector<vector<int>> arr(n + 1, vector<int>(n + 1, 100000));
	vector<edge> elist(m + 1);

	for (int i = 1; i <= n; i++) {
		arr[i][i] = 0;
	}

	for (int i = 1; i <= m; i++) {
		int s, d, v; cin >> s >> d >> v;
		arr[d][s] = arr[s][d] = min(v, arr[s][d]);
		elist[i] = { s, d, v };
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (arr[j][k] > arr[j][i] + arr[i][k]) {
					arr[j][k] = arr[j][i] + arr[i][k];
				}
			}
		}
	}

	float mn = 2100000000;

	for (int i = 1; i <= n; i++) {
		float mx = -1;
		for (int j = 1; j <= m; j++) {
			int st = elist[j].s;
			int de = elist[j].d;
			int val = elist[j].v;		
			float time = (float)(val - abs(arr[i][st] - arr[i][de])) / 2.0 + max(arr[i][st], arr[i][de]);
			if (val + min(arr[i][st], arr[i][de]) < max(arr[i][st], arr[i][de])) {
				time = min(arr[i][st], arr[i][de]) + val;
			}
			mx = mx > time ? mx : time;
		}
		mn = mn < mx ? mn : mx;
	}

	printf("%.1f\n", mn);
    
	return 0;
}