[Floyd] BOJ 13141 Ignition

문제 링크 : www.acmicpc.net/problem/13141

13141번: Ignition

 

간선들은 그 간선의 양 끝 노드에 불이 옮겨진 순간부터 타는 시간이 절반으로 줄어들게 된다.

쉽게 설명하자면 다음 그림과 같다.

정점 A에 불이 먼저 붙은 상황이다. 이 때, A와 B를 잇는 간선은 A쪽에서 먼저 타게 된다.

B쪽에는 아직 불이 도착하지 않았기 때문이다.

이제 정점 B에도 불이 붙었다. 이제는 간선의 남은 길이가 양쪽에서 타게 되므로, 간선이 타는 데 걸리는 시간은 남은 길이의 절반이다.

 

이를 통해 우리는 불이 각 정점에 도달하는 시간이 문제 풀이의 핵심이 되는 것을 알 수 있다. 즉, 최단 거리이다.

마침 문제에서 주어진 정점의 수가 200개로 매우 작기 때문에, 시간복잡도가 O(N^3)인 플로이드-와샬 알고리즘을 사용할 수 있다.

그래프의 정점 간 가장 짧은 간선을 통해 최단거리를 구한 후, 가장 긴 간선을 통해 간선이 타는 데 걸리는 최대 시간을 구하면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
 
int n, m;
int dist[201][201][3];        //0 : 최소간선을 통한 계산결과, 1 : 최대간선, 2 : 최소간선
int selfdist[201];                    //자기 자신에게 돌아오는 간선의 최대길이 저장
 
void floyd() {
    for (int mid = 1; mid <= n; mid++) {
        for (int s = 1; s <= n; s++) {
            for (int e = 1; e <= n; e++) {
                dist[s][e][0] = min(dist[s][e][0], dist[s][mid][0] + dist[mid][e][0]);
            }
        }
    }
}
 
void init() {
    int s, e, l;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            dist[i][j][0] = INF;
        }
 
    for (int i = 0; i < m; i++) {
        cin >> s >> e >> l;
 
        if (s == e) {
            selfdist[s] = max(selfdist[s], l);
            continue;
        }
 
        dist[s][e][0] = min(dist[s][e][0], l);
        dist[s][e][1] = max(dist[s][e][1], l);
        dist[s][e][2] = min(dist[s][e][2], l);
 
        dist[e][s][0] = min(dist[e][s][0], l);
        dist[e][s][1] = max(dist[e][s][1], l);
        dist[e][s][2] = min(dist[e][s][2], l);
    }
}
 
float get_maxtime(int startpoint) {
    float maxlen = 0;
    for (int i = 1; i <= n; i++) {
        //자기 자신을 향하는 간선에 대해 비교
        if (selfdist[i] != 0) maxlen = max(maxlen, (float)((float)dist[startpoint][i][0] + (float)selfdist[i] / 2));
 
        for (int j = 1; j <= n; j++) {
            //만약 최단거리에 사용되지 않은 간선이 존재한다면
            if (dist[i][j][1] > 0 && dist[i][j][2] != dist[i][j][1]) {
                int longer = max(dist[startpoint][i][0], dist[startpoint][j][0]);
                float burntime = (float)((float)dist[i][j][1] - (float)abs(dist[startpoint][i][0] - dist[startpoint][j][0])) / 2;
                maxlen = max(maxlen, (float)longer + burntime);
            }
        }
    }
    return maxlen;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    floyd();
 
    float answer = INF;
    for (int i = 1; i <= n; i++) answer = min(answer, get_maxtime(i));
 
    printf("%.1f\n", answer);
 
    return 0;
}