[백준] 10678 Meeting Time

Bessie와 Elsie가 1에서 출발해 N에서 만나려고한다

간선은 M개가 주어진다(간선은 낮은숫자 ->높으숫자만 가능)

근데 둘이 간선을 지나갈 때의 시간이 다르다

이 때 M에서 만날 수 있는 최소의 시간을 구하는 문제다

N이 16밖에 안되기 때문에 bfs로 모든 경로를 다 구했다

그리고 N까지 가는 시간 중 가장 작은수를 출력하면 답이다!

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int n, m;
void bfs(vector<vector<pair<int, int>>>& Graph, set<int>&S) {
    queue < pair<int, int>> q;
    q.push({ 0,0 });
    while (!q.empty()) {
        int here = q.front().first;
        int cost = q.front().second;
        q.pop();
 
        for (int i = 0; i < Graph[here].size(); i++) {
            int next = Graph[here][i].first;
            int ncost = Graph[here][i].second;
            if (next == n - 1) S.insert(cost + ncost);
            q.push({ next,cost+ncost });
        }
    }
}
int main() {
    scanf(" %d %d", &n, &m);
    vector < vector<pair<int, int>>> aGraph(n), bGraph(n);
    for (int i = 0; i < m; i++) {
        int u, v, a, b; scanf(" %d %d %d %d", &u, &v, &a, &b);
        u--; v--;
        aGraph[u].push_back({ v,a });
        bGraph[u].push_back({ v,b });
    }
    set<int> A, B;
    bfs(aGraph, A);
    bfs(bGraph, B);
    set<int>::iterator it;
    for (it = A.begin(); it != A.end(); it++) {
        if (B.count(*it)) {
            printf("%d\n", *it); return 0;
        }
    }
    puts("IMPOSSIBLE");
}