プログラマGPS

コード#コード#

#include <vector>
#include <algorithm>
#include <iostream>
#define INF 1e9
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    vector<int> graph[201];
    
    for (auto i : edge_list) {
        graph[i[0]].push_back(i[1]);
        graph[i[1]].push_back(i[0]);
    }
    for(int i=1;i<=n;i++) graph[i].push_back(i);
    vector<vector<int>> dp(k, vector<int>(n + 1, INF));

    dp[0][gps_log[0]] = 0;
    for (int i = 0; i < k - 1; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[i][j] == INF) continue;

            for (int k : graph[j]) {
                int re = dp[i][j];
                if (gps_log[i + 1] != k) re++;

                dp[i + 1][k] = min(dp[i + 1][k], re);
            }
        }
    }
    answer = dp[k - 1][gps_log[k - 1]];
    if(answer==INF) return -1;
    
    return answer;
}

に答える

    vector<int> graph[201];

    for (auto i : edge_list) {
        graph[i[0]].push_back(i[1]);
        graph[i[1]].push_back(i[0]);
    }
    for(int i=1;i<=n;i++) graph[i].push_back(i);