Game Develop

[Algorithm]Baekjoon 11404번 : 플로이드 본문

Algorithm/Baekjoon

[Algorithm]Baekjoon 11404번 : 플로이드

MaxLevel 2022. 9. 6. 21:33

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

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
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int vertexCount = 0;
    int edgeCount = 0;
    int a, b, c;
 
    cin >> vertexCount;
    cin >> edgeCount;
 
    vector<vector<int>> graph(vertexCount+1, vector<int>(vertexCount+1,10000000));
 
    for (int i = 1; i <= vertexCount; i++)
    {
        graph[i][i] = 0;
    }
 
    for (int i = 0; i < edgeCount; i++)
    {
        cin >> a >> b >> c;
 
        if(graph[a][b] >= c) graph[a][b] = c;
    }
 
    for (int k = 1; k <= vertexCount; k++)
    {
        for (int i = 1; i <= vertexCount; i++)
        {
            for (int j = 1; j <= vertexCount; j++)
            {
                if (graph[i][k] + graph[k][j] <= graph[i][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
 
    for (int i = 1; i <= vertexCount; i++)
    {
        for (int j = 1; j <= vertexCount; j++)
        {
            if (graph[i][j] == 10000000) graph[i][j] = 0;
            cout << graph[i][j] << ' ';
        }
        cout << endl;
    }
}
 cs

 

플로이드와샬 기본예제문제다. 

 

'Algorithm > Baekjoon' 카테고리의 다른 글

[Algorithm]Baekjoon 2606번 :: 바이러스  (0) 2022.09.12
[Algorithm]Baekjoon 1707번 : 이분 그래프  (0) 2022.09.11
[Algorithm]Baekjoon 15988번 : 1,2,3 더하기 3  (0) 2022.09.05
[Algorithm]Baekjoon 9095번 : 1,2,3 더하기  (0) 2022.09.05
[Algorithm]Baekjoon 2667번 : 단지번호붙이기  (0) 2022.08.08
'Algorithm/Baekjoon' Related Articles more