Baekjoon 11404번 플로이드

문제

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

걸린 시간

00 : 15 : 23

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    int a, b, c;
    vector<vector<int>> adj(n, vector<int>(n, INF));
    for(int i = 0; i < n; i++)
        adj[i][i] = 0;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        if(adj[a-1][b-1] > c)
            adj[a-1][b-1] = c;
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            if(adj[i][j] == INF) cout << 0 << " ";
            else cout << adj[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

문제 이름 그대로 플로이드 와샬 알고리즘 문제이다.

시작도시와 도착도시를 연결하는 노선이 하나가 아닐 수 있다는 조건만 유의해서 플로이드 와샬 알고리즘을 구현하면 ac를 받을 수 있다.