[코드트리] 이동 가능한 점들의 쌍 C++

문제

https://www.codetree.ai/missions/8/problems/pair-of-points-that-can-be-moved?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 쪼개기

주어지는 것

1부터 N까지 번호가 붙은 N개의 서로 다른 점

이 점들 중 임의의 두 점을 잇는 M개의 길

N개의 점 중 1번부터 P번까지의 점은 빨간점

 

조건

모든 길은 한 방향으로만 이동(방향 그래프)

특정 두 점을 잇고 특정 방향으로 이동 가능한 길은 최대 1개만 존재(중복 간선은 주어지지 않음)

M개의 길들을 이용해 주어진 점A으로부터 점B까지 최소 비용으로 이동

이때, 출발점과 도착점을 포함해 이동 경로 내에 적어도 하나 이상의 빨간점이 포함되어 있어야 합니다.

한 개의 점을 여러 번 방문해도 괜찮고, 각 길을 통해 이동할 때 드는 비용은 상이하며 이 비용 값은 주어집니다.

 

목표

주어진 출발점과 도착점들 쌍 Q개 중 빨간색 점을 최소 하나 이상 지나 갈 수 있는 경우가 몇 개인지를 구하고, 가능한 경우에 대해 각 최소 비용의 총 합을 구하는 프로그램을 작성해보세요.

 

코드

#include <iostream>
using namespace std;

const int MAX_N = 201;

int n, m, p, q;
int graph[MAX_N][MAX_N];

// [초기화]
void Init(){
    // 1. graph를 1e9로 초기화
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            graph[i][j]=1e9;
        }
        graph[i][i]=0;
    }
}

int main() {

    // [입력] m개의 graph[s][e]=c;
    cin >> n >> m >> p >> q;
    // [초기화]
    Init();
    for(int i=0; i<m; ++i){
        // 출발점 번호, 도착점 번호, 비용
        int s, e, c;
        cin >> s >> e >> c;
        graph[s][e]=c;
    }

    // solution
    for(int k=1; k<=n; ++k){
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=n; ++j){
                graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }

    // q개의 출발 도착점에 대해 
    long long numOfRoute=0, sumOfCost=0;
    while(q--){
        int s, e;
        cin >> s >> e;

        // 빨간점(1~p)를 적어도 1개 반드시 포함해야 한다.
        int dist = 1e9;
        for(int i=1; i<=p; ++i){
            dist=min(dist, graph[s][i]+graph[i][e]);
        }

        // 불가능하다면 패스
        if(dist==1e9) continue;

        numOfRoute++;
        sumOfCost+=dist;
    }

    // output
    cout << numOfRoute << '\n' << sumOfCost <<'\n';
    return 0;
}