#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
vector<pair<int, int>> graph[20001];
long long check[20001];
struct compare
{
    bool operator()(pair<int, int> s1, pair<int, int> s2)
    {
        return s1.second < s2.second;
    }
};
void dikstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;
    q.push({start, 0});
    while (!q.empty())
    {
        int node = q.top().first;
        int dis = -q.top().second;
        q.pop();
        if (dis > check[node])
            continue;
        auto list = graph[node];
        for (int i = 0; i < list.size(); i++)
        {
            int nextnode = list[i].first;
            int nextcost = list[i].second;
            if (check[nextnode] > dis + nextcost)
            {
                check[nextnode] = dis + nextcost;
                q.push({nextnode, -check[nextnode]});
            }
        }
    }
}
int main(void)
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int v, e;
    cin >> v >> e;
    int start;
    cin >> start;
    for (int i = 0; i < e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    for (int i = 1; i <= v; i++)
    {
        check[i] = INF;
    }
    check[start] = 0;
    dikstra(start);
    for (int i = 1; i <= v; i++)
    {
        if (check[i] >= INF)
            cout << "INF"
                 << "\n";
        else
            cout << check[i] << "\n";
    }
    return (0);
}

다익스트라를 다시 구현해 보고 싶어서 풀어봤는데 시간초과로 되게 해맸다...;;

틀린 이유

fastio

입출력에 의해 시간 초과가 날 수 있다.

 cin.tie(NULL);
    ios_base::sync_with_stdio(false);

이 코드를 추가 시켜 줘야 한다.

https://www.acmicpc.net/problem/15552

우선 순위 큐 정렬 방식

우선순위 큐에 { 노드번호, 가중치 } 순서로 넣으면 정렬이 노드 번호가 작은 순서, 같으면 가중치가 작은 순서로 우선순위 큐가 작동하기 때문에 생각하신 대로 동작하지 않는다 .비교 함수를 직접 작성해 넣으시거나 { 가중치, 노드번호 } 순으로 넣어야 한다.
다음과 같은 코드를 추가 시켜 주었다.

struct compare
{
    bool operator()(pair<int, int> s1, pair<int, int> s2)
    {
        return s1.second < s2.second;
    }
};
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;