백준 6185번: Clear And Present Danger (C++)

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

6185번: Clear And Present Danger

---

Level: Gold V

Solved By: Floyd Warshall

 

특정 sequence를 지나쳐야 하기에 이 정보들을 담아주었고, 모든 노드에 대한 N:N 최단 경로 정보가 필요했기 때문에 Floyd Warshall을 사용하여 풀었습니다.

#include <iostream>
#include <vector>
#define MAX 101
using namespace std;

int N, M;
vector<int> sequence;
int graph[MAX][MAX];

void floydWarshall(){
    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if(i == k || k == j) continue;
                if(graph[i][k] + graph[k][j] < graph[i][j]){
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int v; cin >> v;
        sequence.push_back(v);
    }
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> graph[i][j];
        }
    }
    
    floydWarshall();
    
    int res = 0;
    
    for(int i = 1; i < sequence.size(); i++){
        res += graph[sequence[i - 1]][sequence[i]];
    }
    
    cout << res;
    return 0;
}