Baekjoon 1976번 여행 가자

문제

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

걸린 시간

00 : 21 : 18

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int adj[200][200];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            cin >> adj[y][x];
            if(adj[y][x] == 0) adj[y][x] = INF;
        }
    }
    for(int i = 0; i < n; i++) adj[i][i] = 0;
    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]);
    vector<int> plan(m);
    for(auto& i : plan) cin >> i;
    for(int i = 0; i < m-1; i++){
        if(adj[plan[i]-1][plan[i+1]-1] == INF){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}

한 도시에서 다른 도시로 이동이 가능한지를 순서대로 살펴보면 된다.

플로이드 와샬 알고리즘으로 한번에 이동 가능 여부를 모두 조사하여 풀이했다.