---
tags: 圖論
title: Dijkstra
---

# Dijkstra
[ZJ c125](https://zerojudge.tw/ShowProblem?problemid=c125)
[Atcoder Beginner contest 192 E](https://atcoder.jp/contests/abc192/tasks/abc192_e)

priority_queue<T> pq1;
priority_queue<T, vector<T>, greater<T> > pq2;

T a;
pq1.push(a);//把a放進queue裡 O(logN)
T b = pq1.top();//b是queue裡面最大值 O(1)
T c = pq2.top();//c是queue裡面最小值 O(1)
pq1.pop();//把queue中最大的清掉 O(logN)
pq1.empty();
pq1.clear();

pair<int, int> P1, P2;
P1 = make_pair(1,2), P2 = make_pair(2,1);
P1.first;//1
P1.second;//2

struct status{
    int num;//點編號
    int weight;//從一至num的最短路徑
    bool operator<(const status &rhs)const{
        return weight < rhs.weight;
    }
};

priority_queue
<
    pair <int,int>,
    vector <pair <int,int> >,
    greater <pair <int,int> >
> pq;

vector<int> edge[N];
vector<int> weight[N];
int dist[N] = {0};

pq.push(make_pair(0, 1));
while(!pq.empty()){
    pair<int,int> cur = pq.top();//將最小的狀態拿出來
    pq.pop();
    int len = cur.first;
    int num = cur.second;
    if(dist[num] != 0){
        continue;
    }
    dist[num] = len;
    for(int i = 0; i < edge[num].size(); ++i){
        if(dist[edge[num][i] != 0]){
            continue;
        }
        pair<int,int> nxt = make_pair(len+weight[num][i], edge[num][i]);
        pq.push(nxt);
    }
}

dist 1 2 3 4 5 6
val 0 8 4 16 11 10

queue = {(17, 4)}
cur = (16, 4)

設共有V個點E個邊
Time Complexity: $O((V+E)log{V})$