[코드트리] 저렴한 모임 C++

문제

https://www.codetree.ai/missions/8/problems/cheapest-meeting?&utm_source=clipboard&utm_medium=text

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

 

문제 쪼개기

주어지는 것

n개의 정점과 m개의 간선

A의 출발점 v1, B의 출발점 v2, 도착지 e

목표

두 사람이 정점 e에 도착하기 위해 지불해야 하는 비용 중 최소 비용

조건

n개의 정점과 m개의 간선으로 이루어져 있는 양방향 그래프

사람 A는 정점 v1​, 사람 B는 정점 v2​에서 출발하여 정점 e로 이동

이동 방법은 택시를 이용하는 것이며, 각 간선마다 택시 이용시 추가로 부가되는 비용이 정해져 있습니다. 

단, 사람 A와 사람 B가 원한다면 도중에 특정 지점에서 만나서 동일한 택시를 타고 함께 이동하는 것이 가능

동일한 거리를 여러 번 지나는 것 역시 가능하며 이때는 추가적으로 비용이 부과

 

코드

#include <iostream>
using namespace std;

const int MAX_N=101;

int n, m, v1, v2, e;
int graph[MAX_N][MAX_N];

void Init(){
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            graph[i][j]=1e9;
        }
        // 자기자신으로 가는 비용은 0
        graph[i][i]=0;
    }
}

int main() {
    // input
    cin >> n >> m;
    Init();
    cin >> v1 >> v2 >> e;
    for(int i=0; i<m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        // 양방향 그래프
        graph[a][b]=c;
        graph[b][a]=c;
    }

    // 최단거리 갱신
    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]);
            }
        }
    }

    int answer = 1e9;
    for(int k=1; k<=n; ++k){
        // (v1->k)+(v2->k)+(k->e)의 최소 비용을 구하면 됨
        answer = min(answer, graph[v1][k]+graph[v2][k]+graph[k][e]);
        
    }
    // 불가능 하다면 -1 출력
    if(answer==1e9) answer=-1;

    cout << answer << '\n';
    return 0;
}