간단한 기본 다익스트라 구현

#define MAX 10000+1
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 987654321;
vector<pii> adj[MAX];
 
void dijk(int start) {
    int dist[MAX];
    fill(dist, dist + MAX, INF); //닫힌시작 열린끝
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({ 0,start });
    while (!pq.empty()) {
        pii t = pq.top();
        pq.pop();
        int here = t.second;
        int cost = t.first;
        if (dist[here] != cost) continue; // dist[here] < cost인 경우만 존재.
        for (pair<int, int> &p : adj[here]) {
            int there = p.first;
            int there_cost = p.second;
            if (dist[there] > cost + there_cost) {
                dist[there] = cost + there_cost;
                pq.push({ cost + there_cost,{there}});
            }
        }
    }
}
 

 for (pair<int, int> &p : adj[here]) == for(int i=0;i<adj[here].size();i++) pii p=adj[here][i];

2.시간복잡도 O(V^2) V는 정점의 개수

void dijk(int start) {
    int dist[MAX];
    fill(dist, dist + MAX, INF); //닫힌시작 열린끝
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({ 0,start });
    parent[start] = -1; // 정점 start는 최적의 전 경로가 없음
 
    for(int k=0;k<n;k++){
        int here, cost = INF;
        for (int i = 0; i < MAX; i++) {
            if (dist[i] < cost &&visited[i] == 0) {
                here = i;
                cost = dist[i];
            }
        }
        visited[i] = 1;
        for (pair<int, int> &p : adj[here]) {
            int there = p.first;
            int there_cost = p.second;
            if (dist[there] > cost + there_cost) {
                dist[there] = cost + there_cost;
                parent[there] = here; //최적의 경로 업데이트 해주기
                pq.push({ cost + there_cost,{there}});
            }
        }
    }
}