백준 1753 최단경로 C++

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

다익스트라 알고리즘을 구현해주면 된다.

방문했던 노드를 다시 방문하지 않도록 해주어야 TLE를 피할 수 있을 것이다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<limits.h>
using namespace std;
int n, m, dist[20001];
 
typedef pair<int, int> pii;
bool vis[20001];
vector<pii> e[20001]; //비용, 목적지
priority_queue<pii, vector<pii>, greater<pii> > pq;
void dijkstra(int st) {
    dist[st] = 0;
    
    pq.push({ dist[st], st });
 
    while (!pq.empty()) {
        int here = pq.top().second;
        vis[here] = true;
        
        pq.pop();
        for (int i = 0; i < e[here].size(); i++) {
            int there = e[here][i].second;
            if (vis[there]) continue;
            int moveCost = e[here][i].first;
            if (dist[there] > dist[here] + moveCost) {
                dist[there] = dist[here] + moveCost;
                pq.push({ dist[there], there });
                
            }
        }
    }
}
int main() {
    cin >> n >> m;
    int src;
    cin >> src;
    while (m--) {
        int from, to, cost;
        cin >> from >> to >> cost;
        e[from].push_back({ cost, to });
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    
 
    dijkstra(src);
    
    for (int i = 1; i <= n; i++) {
        if (dist[i] != INT_MAX) cout << dist[i] << '\n';
        else cout << "INF" << '\n';
    }
    return 0;
}