[BOJ] 플로이드

[문제]

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

11404번: 플로이드

[풀이]

 

11404

맞았습니다!!

2028

24

C++14 / 수정

934

35초 전

 

1) 제목부터 플로이드 와셜 알고리즘을 쓰라고 되어있어서 플로이드 와셜 알고리즘을 사용한다. 

 

2) 굳이 헷갈릴 수 있는 점을 뽑자면 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."

 

---

#include <iostream>
#include <vector>
 
#define MAX_M 100001
#define INF 987654321
 
using namespace std;
 
//플로이드
// typedef pair<int, int> pp;
int res[101];
int bus_fee[101][101];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j) bus_fee[i][j] = 0;
            else bus_fee[i][j] = INF;
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        bus_fee[a][b] = bus_fee[a][b] > c ? c : bus_fee[a][b];
    }
    //input
 
    for (int a = 1; a <= n; a++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                bus_fee[i][j] = min(bus_fee[i][j], bus_fee[i][a] + bus_fee[a][j]);
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (bus_fee[i][j] == INF) cout << 0 << " ";
            else cout << bus_fee[i][j] << " ";
        }
        cout << '\n';
    }
 
    return 0;
}