适用范围

单源正权边最短路
时间复杂度O(n^2)

模板

稠密图(n^2)

Dijkstra求最短路 I

#include
#include
#include

using namespace std;

const int N = 510;

int d[N][N];        //两点之间的距离
int dist[N];        //点到1之间的距离
bool st[N];         //点是否为确定最短路点

int n,m;

int dj(){
    //将1点距离设置为0，其余点设置为无穷大
    memset(dist,0x3f,sizeof dist);

    dist[1] = 0;

    //将每一点最近的点最短路确立
    for(int i = 0;i < n;i ++){
        int t = -1;

        for(int j = 1;j <= n;j ++)
            if(!st[j] &&  (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 1;j <= n;j ++)
            dist[j] = min(dist[j],dist[t] + d[t][j]);
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n]; 
}

int main(){
    cin >> n >> m;

    memset(d,0x3f,sizeof d);

    while(m --){
        int a,b,c;
        cin >> a >> b >> c;

        d[a][b] = min(d[a][b],c);
    }

    cout << dj();
}

稀疏图(mlogn)

Dijkstra求最短路 II

STL小根堆

#include
#include
#include
#include

using namespace std;

const int N = 200010;

typedef pair p;

//稀疏图用邻接表存
int e[N],ne[N],w[N],idx,h[N];
int dist[N];
bool st[N];

int n,m;

//连边加权
void add(int a,int b,int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dj(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

//小根堆构造
    priority_queue,greater
> heap;
//初始位置入队
    heap.push({0,1});
//更新所有节点最短路
    while(heap.size()){
        auto t= heap.top();
        heap.pop();

        int ver = t.second,distance = t.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver];i != -1;i = ne[i]){
            int j = e[i];

            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;

    memset(h,-1,sizeof h);

    while(m --){
        int a,b,c;
        cin >> a >> b >> c;

        add(a,b,c);
    }

    cout << dj();
}

手写小根堆

#include
#include
#include

using namespace std;

typedef pair p;
const int N = 200010;

p heap[N];
int cnt;
int e[N],ne[N],w[N],h[N],idx;
int dist[N];
bool st[N];

int n,m;

void down(int u){
    int t = u;
    if(u * 2 <= cnt && heap[u * 2].first < heap[t].first) t = u * 2;
    if(u * 2 + 1 <= cnt && heap[u * 2 + 1].first < heap[t].first) t = u * 2 + 1;

    if(u != t){
        swap(heap[t],heap[u]);
        down(t);
    }
}

void up(int u){
    if(u / 2 && heap[u / 2].first > heap[u].first){
        swap(heap[u / 2],heap[u]);
        up(u / 2);
    }
}

void add(int a,int b,int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dj(){
    memset(dist,0x3f,sizeof dist);

    dist[1] = 0;
    heap[++ cnt] = {0,1};

    while(cnt){
        auto t = heap[1];
        swap(heap[1],heap[cnt]);
        cnt --;
        down(1);

        int ver = t.second,distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver];i != -1;i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap[++ cnt] = {dist[j],j};
                up(cnt);
                down(cnt);
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;

    memset(h,-1,sizeof h);

    while(m --){
        int a,b,c;
        cin >> a >> b >> c;

        add(a,b,c);
    }

    cout << dj();
}