简单纯单源最短路问题

https://www.luogu.com.cn/problem/P4779

必须存距离+位置

Dijkstra算法（这是最快的方法）

#include <bits/stdc++.h>

#define ll long long
#define PII std::pair<ll,ll>
const ll N = 1e6 + 10;
ll n;
ll e[N],ne[N],idx,w[N],h[N];
ll dis[N];
bool ok[N];

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

void jl(ll aa){
    dis[aa] = 0;
    std::priority_queue<PII,std::vector<PII>,std::greater<PII>> op;
    op.push({dis[aa],aa});
    while(op.size()){
        auto jj = op.top();
        op.pop();
        ll x1 = jj.first;
        ll x2 = jj.second;
        if(ok[x2] == true) continue;
        ok[x2] = true;
        for(ll i = h[x2]; i != -1; i = ne[i]){
            auto jk = e[i];
            if(dis[jk] > x1 + w[i]){
                dis[jk] = x1 + w[i];
                op.push({dis[jk],jk});
//              ok[jk] = true;
            }
        }
    }
}

int main(){
    ll n,m,s;
    std::cin >> n >> m >> s;
    for(ll i = 1; i <= n + 10; i ++) h[i] = -1;
    for(ll i = 1; i <= m; i ++){
        ll a,b,c;
        std::cin >> a >> b >> c;
        add(a,b,c);
    }
    for(ll i = 1; i <= n; i ++) dis[i] = 1e11;
    jl(s);
    for(ll i = 1; i <= n; i ++) std::cout << dis[i] << " ";
    std::cout << "\n";
    return 0;
}

spfa算法（这个相对上一个慢，有数据会超时）

但是spfa是能够解决负权问题的

#include <bits/stdc++.h>

#define ll long long
#define PII std::pair<ll,ll>
const ll N = 1e6 + 10;
ll n;
ll e[N],ne[N],idx,w[N],h[N];
ll dis[N];
bool ok[N];

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

void jl(ll aa){
    std::queue<ll> op;
    op.push(aa);
    dis[aa] = 0;
    ok[aa] = true;
    while(op.size()){
        auto jj = op.front();
        op.pop();
        ok[jj] = false;
        for(ll i = h[jj]; i != -1; i = ne[i]){
            ll jk = e[i];
            if(dis[jk] > dis[jj] + w[i]){
                dis[jk] = dis[jj] + w[i];
                if(ok[jk] == false){
                    op.push(jk);
                    ok[jk] = true;
                }
            }
        }
    }
}

int main(){
    ll n,m,s;
    std::cin >> n >> m >> s;
    for(ll i = 1; i <= n + 10; i ++) h[i] = -1;
    for(ll i = 1; i <= m; i ++){
        ll a,b,c;
        std::cin >> a >> b >> c;
        add(a,b,c);
    }
    for(ll i = 1; i <= n; i ++) dis[i] = 1e11;
    jl(s);
    for(ll i = 1; i <= n; i ++) std::cout << dis[i] << " ";
    std::cout << "\n";
    return 0;
}

单源最短路的分层图问题

https://www.luogu.com.cn/problem/P4568

分层图 + Dijkstra算法（不可能会出现负值）

//分层图最短路
#include <bits/stdc++.h>

#define ll long long
#define PII std::pair<ll,ll>
const ll N = 3e6;
ll n,m,k;
ll s,t;
ll h[N],e[N],ne[N],idx,w[N];
ll dis[N];
bool ok[N];

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

void jl(ll aa){
    std::memset(dis,0x3f,sizeof dis);
    dis[aa] = 0;
    std::priority_queue<PII,std::vector<PII>,std::greater<PII>> op;
    op.push({dis[aa],aa});
    while(op.size()){
        auto jj = op.top();
        op.pop();
        ll a = jj.first;
        ll b = jj.second;
        if(ok[b] == true) continue;
        ok[b] = true;
        for(ll i = h[b]; i != -1; i = ne[i]){
            ll jr = e[i];
            if(dis[jr] > w[i] + dis[b]){
                dis[jr] = w[i] + dis[b];
                op.push({dis[jr],jr});
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    std::cin >> n >> m >> k;
    std::cin >> s >> t;
//  for(ll i = 1; i <= 2e6; i ++) h[i] = -1;
    std::memset(h,-1,sizeof h);
    for(ll i = 1; i <= m; i ++){
        ll a,b,c;
        std::cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
        for(ll j = 1; j <= k; j ++){
            add(a + (j - 1) * n,b + j * n,0);
            add(b + (j - 1) * n,a + j * n,0);
            add(a + j * n,b + j * n,c);
            add(b + j * n,a + j * n,c);
        }
    }
    for(ll i = 1; i <= k; i ++){
        add(t + (i - 1) * n,t + i * n,0);
    }
    jl(s);
    std::cout << dis[t + k * n] << "\n";
    return 0;
}