문제

문제 링크

문제 접근

  • 이 문제는 가장 작은 바용으로 도착지점까지 도착해야 하는 문제로 다익스트라를 이용해서 쉽게 풀었다!
  • priority queue가 내림 차순으로 sorting 되기 때문에 비용에 음수를 취해 사용했다.

코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define pll pair<ll, ll>

ll ans, cnt, n, m, v1, v2, w, src, dst, visited[1001];
vector<vector<pll> > e;
int main(){
    scanf("%lld %lld", &n, &m);
    e = vector<vector<pll> >(n+1);
    for(int i = 0; i < m; i++){
        scanf("%lld %lld %lld", &v1, &v2, &w);
        e[v1].push_back(pll(-w, v2));
    }
    scanf("%lld %lld", &src, &dst);
    priority_queue<pll> pq;
    pq.push(pll(0, src));
    while(!pq.empty()){
        pll top = pq.top(); pq.pop();
        int tv = top.first, tx = top.second;
        visited[tx] = 1, cnt++;
        if(tx == dst){
            ans = tv;
            break;
        }
        for(int i = 0; i < e[tx].size(); i++){
            pll next = e[tx][i];
            int nv = next.first, nx = next.second;
            if(visited[nx])continue;
            pq.push(pll(tv + nv, nx));
        }
    }
    printf("%lld", -ans);

}

느낀점

  • 다익스트라를 통해서 확실히 쉽게 풀어낼 수 있었다!
  • 다익스트라 구현은 실수만 없다면 잘 할 수 있을 것 같다…!