[알고리즘] 그래프 - 최단거리 구하기(cpp)

N개의 노드와 M개의 에지가 있는 그래프에서, 세 노드 s, a, t가 주어졌을 때 s에서 a를 반드시 지나서 t까지 도달하는 가장 짧은 거리를 구하는 프로그램을 작성하시오. 

입력 
표준 입력으로 입력을 받는다. 첫 줄에는 노드의 개수 N과 에지의 개수 M이 주어진다. 노드의 개수는 3 이상 100 이하이고, 에지의 개수는 0개 이상 N(N-1)개 이하이다. 
두번째 줄에는 세 정수 s a t가 주어진다. 노드들은 0 이상 N 미만인 정수들로 표현되며, 이 세정수는 각각 시작 노드, 중간 노드, 도착 노드를 나타낸다. 
세번째 줄부터 총 M줄에 에지 정보가 주어진다. 한 줄은 에지 하나에 대한 정보를 나타내며, 세 정수 U V W로 이루어진다. U는 에지의 시작 노드, V는 에지의 도착 노드, W는 에지의 가중치이다. 이 그래프는 유향 그래프이며 에지의 가중치는 -100 이상 100 이하인 정수이다. U=V, 즉 자신에서 자신으로 이어지는 에지는 없으며, 이 그래프에는 음의 가중치를 갖는 사이클이 없다.

출력 
표준 출력으로 출력한다. 한 줄로 출력하고, 이 줄에는 s에서 a를 거쳐 b로 가는 최단 거리를 출력한다.    

예제 입력 
4 6
0 2 3
0 1 2
0 2 3
0 3 1
1 2 -1
1 3 4
2 3 2
예제 출력 
3

---

 

bfs/dfs 문제 한번도 안 풀어봤을 때 나온 그래프 과제...

이때는 bfs가 어려워서 그냥 반복문으로 열심히 풀었다.

과거의 멍청한 나,, 그래도 만점 받은거 보면 꽤나 똑똑했을지도

 

"음의 가중치를 갖는 '사이클'이 없다"라고 했으므로 Bellman Ford 알고리즘을 썼던걸로 기억한다.

s->a의 최단거리를 구하고, a->t의 최단거리를 구해서 더해주었다.

 

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int dist[101];
 
struct Edge {
    int s;
    int e;
    int val;
    Edge(int u, int v, int w) {
        s = u;
        e = v;
        val = w;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m; // 노드, 에지
    int s, a, t; // 시작, 중간, 도착
    int u, v, w; // 에지 시작노드, 에지 도착노드, 가중치
    cin >> n >> m >> s >> a >> t;
    vector<Edge> ed;

    for (int i = 0; i < m; ++i){
        cin >> u >> v >> w;
        ed.push_back(Edge(u, v, w));
    }

    for (int i = 0; i < n+1; i++) {
        dist[i] = 100000;
    }
    dist[s] = 0;
    for (int i = 0; i < n+1; i++) {
        for (int j = 0; j < ed.size(); j++) {
            int start = ed[j].s;
            int end = ed[j].e;
            int wei = ed[j].val;
            int newWei = dist[start] + wei;
            if (dist[start] != 100000 && newWei < dist[end]) {
                dist[end] = newWei;
            }
        }
    }
    // cout << "s_to_a = "<< dist[a] << "\n";
    int s_to_a = dist[a];
    if(s_to_a == 100000) { // 경유지에 갈 수 없을 때 예외처리
        exit(0);
    } 

    //
    for (int i = 0; i < n+1; i++) {
        dist[i] = 100000;
    }
    dist[a] = 0;
    for (int i = 0; i < n+1; i++) {
        for (int j = 0; j < ed.size(); j++) {
            int start = ed[j].s;
            int end = ed[j].e;
            int wei = ed[j].val;
            int newWei = dist[start] + wei;
            if (dist[start] != 100000 && newWei < dist[end]) {
                dist[end] = newWei;
            }
            
        }
    }
    // cout << "a_to_t = " << dist[t]<<"\n";
    int a_to_t = dist[t];
    if (a_to_t == 100000)
    { // 경유지에서 도착점으로 갈 수 없을 때 예외처리
        exit(0);
    }
    cout << s_to_a + a_to_t;
    return 0;
}