[BOJ] 1916 최소비용 구하기

문제: https://www.acmicpc.net/problem/1916

 그냥 다익스트라 그 자체이다. 풀이를 설명할 필요가 있을까? 난이도는 1.5/5

#include <cstdio>
#include <vector>
#include <queue>
#define INF (2100000000)
 
using namespace std;
 
int main()
{
    int n,m,st,en;
    scanf("%d %d",&n,&m);
 
    priority_queue<pair<int,int> > Q;
    vector<vector<pair<int,int> > > lis(n+1,vector<pair<int,int> >());
    vector<int> dist(n+1,INF);
 
    for(int i=0;i<m;i++)
    {
        int t1,t2,weight;
        scanf("%d %d %d",&t1,&t2,&weight);
        lis[t1].push_back(make_pair(weight,t2));
    }
 
    scanf("%d %d",&st,&en);
    dist[st]=0;
    Q.push(make_pair(0,st));
    while(!Q.empty())
    {
        int ndist=-Q.top().first;
        int here=Q.top().second;
        Q.pop();
        if(ndist>dist[here]) continue;
        for(int i=0;i<lis[here].size();i++)
        {
            int there=lis[here][i].second;
            int tdist=lis[here][i].first;
            if(dist[there]>ndist+tdist)
            {
                dist[there]=ndist+tdist;
                Q.push(make_pair(-dist[there],there));
            }
        }
    }
    printf("%d",dist[en]);
    return 0;
}