1753번-최단경로

문제

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

1753번: 최단경로

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int INF = 987654321;
const int MAX = 200001;
vector<pair<int,int>> edge[MAX];
int v, e;
int start;
int main(void)
{
    fastio;
    cin >> v >> e >> start;
 
    for(int i = 0; i < e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({w, v});
    }
 
    auto dijkstra = [&](int start) -> vector<int>{
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, start});
        vector<int> dist(v + 1, INF);
        dist[start] = 0;
 
        while(!pq.empty())
        {
            int cur = pq.top().second;
            int cost = pq.top().first;
            pq.pop();
 
            if (dist[cur] < cost)
                continue;
 
            for(auto idx : edge[cur])
            {
                int neighbor = idx.second;
                int neighborCost = idx.first + cost;
 
                if(dist[neighbor] > neighborCost)
                {
                    dist[neighbor] = neighborCost;
                    pq.push({neighborCost, neighbor});
                }
            }
        }
        return dist;
            };
 
    vector<int> ret = dijkstra(start);
    for(int i = 1; i < ret.size(); i++)
    {
        if(ret[i] != INF)
            cout << ret[i] << "\n";
        else
            cout << "INF" << "\n";
    }
    return 0;
}