백준 11780 플로이드2

작성일 | In |

Problem : 플로이드2

유형 : 플로이드 워셜

문제 해석

  • 각 도시별 최단 거리를 찾아라.

문제 재해석

  • 도시별로 이동하는 가중치가 있다.
  • 음수인 가중치가 없다.
  • 최단 거리를 찾는다.

해결 전략

  • 플로이드 워셜 알고리즘을 통해 해결한다.
  • 경로의 경우, 최단 거리가 갱신 되는 경우, 경로를 갱신해준다.

설계, 구현

  • table을 만들어 둔다.
  • 아직 경로를 찾지 못한 경우는 최대 (10000 * 100)가 될 수 있는 1e7로 초기화 해둔다.
  • overflow에 주의한다.
  • 자기 자신으로 가는 경우는 0으로 해둔다.
  • 중간에 거치는 도시 가 있는 경우가 최소 거리가 될 수 있는지 매번 따져본다.

주의할 점

  • 같은 방향의 간선이 여러개 일 수 있다.

디버깅

  • 경로를 갱신할 때 실수를 했다.
  • A 에서 Z를 거친 후 B로 가는 것이 최소 비용일때
  • path[A][B] = Z and path[Z][B] = B :x:
  • path[A][B] = path[A][Z] :o:

코드

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7 + 2;
int cost[102][102], path[102][102];
int n;

void Make_Path_Vec(int s, int e) {
    vector<int> path_vec;
    
    while (s != e) {
        path_vec.push_back(s);
        s = path[s][e];
    }
    path_vec.push_back(s);

    cout << (int)path_vec.size() << " ";
    for (const auto& it : path_vec) {
        cout << it << " ";
    }
    cout << "\n";
}

void Print_Path() {

    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= n; ++ii) {
            if (cost[i][ii] == INF or i == ii) cout << 0 << "\n";
            else Make_Path_Vec(i, ii);
        }
    }
}

void Print_Answer() {
    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= n; ++ii) {
            if (cost[i][ii] == INF) cout << 0 << " ";
            else cout << cost[i][ii] << " ";
        }
        cout << "\n";
    }
}

void Solve() {
    for (int visit = 1; visit <= n; ++visit) {
        for (int s = 1; s <= n; ++s) {
            for (int e = 1; e <= n; ++e) {

                if(cost[s][visit] + cost[visit][e] < cost[s][e]){
                    cost[s][e] = cost[s][visit] + cost[visit][e];

                    path[s][e] = path[s][visit];
                    //path[s][e] = visit;
                    //path[visit][e] = e;
                }
            }
        }
    }
    Print_Answer();
    Print_Path();
}

void Init() {
    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= n; ++ii) {
            if (i == ii) continue;
            cost[i][ii] = INF;
        }
    }
}

void Input(){
    cin >> n;

    Init();

    int m;
    cin >> m;
    while (m--) {
        int a, b, bus_cost;
        cin >> a >> b >> bus_cost;
        
        if (bus_cost < cost[a][b]) {
            cost[a][b] = bus_cost;
            path[a][b] = b;
        }
    }
    Solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();

    return 0;
}

피드백

  • 경로 추적시 실수를 다시 하지 않도록 주의 하자.