백준13141 Ignition

작성일 | In

문제 링크

  • http://icpc.me/13141

사용 알고리즘

  • 플로이드

시간복잡도

  • $O(N^3 + NM)$

풀이

정점 $a, b$를 연결하는 가중치가 $c$인 간선이 모두 타는 시간은 ( (시작점에서 $a$까지 도달하는 시간) + (시작점에서 $b$까지 도달하는 시간) + $c$ ) / 2로 계산할 수 있습니다.
그러므로 Floyd-Warshall Algorithm을 이용해서 모든 정점 사이의 거리를 전처리한 뒤, $N$개의 시작점에 대해 $M$개의 간선을 모두 확인해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

int N, M, D[222][222], S[20202], E[20202]; ll X[20202];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    memset(D, 0x3f, sizeof D);
    for(int i=1; i<=N; i++) D[i][i] = 0;
    for(int i=1; i<=M; i++){
        cin >> S[i] >> E[i] >> X[i];
        D[S[i]][E[i]] = min<int>(D[S[i]][E[i]], X[i]);
        D[E[i]][S[i]] = min<int>(D[E[i]][S[i]], X[i]);
    }
    for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

    ll mn = 0x3f3f3f3f3f3f3f3f;
    for(int i=1; i<=N; i++){
        ll mx = 0;
        for(int j=1; j<=M; j++) mx = max(mx, D[i][S[j]] + D[i][E[j]] + X[j]);
        mn = min(mn, mx);
    }
    cout << mn/2 << "." << mn%2*5;
}