dijkstra

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;
const int N = 1e4 + 10,M = 2e5 + 10;
typedef pair<int,int> PII;
int h[N],e[M],ne[M],w[M],idx;
int st[N],d[N];
int n,m;

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

void dijkstra(){
    memset(d,0x3f,sizeof d);
    d[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second,dis = t.first;

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

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

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

int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }
    dijkstra();
    int ans = 0;
    for(int i = 2;i <= n;i++){
        int res = 0x3f3f3f3f;
        for(int j = h[i];j != -1;j = ne[j]){
            int k = e[j];
            if(d[i] == d[k] + w[j]){
                res = min(res,w[j]);
            }
        }
        ans += res;
    }
    cout << ans << endl;
    return 0;
}

spfa

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;
const int N = 1e4 + 10,M = 2e5 + 10;
typedef pair<int,int> PII;
int h[N],e[M],ne[M],w[M],idx;
int st[N],d[N];
int n,m;

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

void spfa(){
    memset(d,0x3f,sizeof d);
    d[1] = 0;
    queue<int> heap;;
    heap.push(1);
    st[1] = 1;
    while(heap.size()){
        int t = heap.front();
        heap.pop();

        st[t] = 0;

        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];
                if(!st[j]){
                    heap.push(j);
                    st[j] = 1;
                }
            }
        }
    }
}

int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }
    spfa();
    int ans = 0;
    for(int i = 2;i <= n;i++){
        int res = 0x3f3f3f3f;
        for(int j = h[i];j != -1;j = ne[j]){
            int k = e[j];
            if(d[i] == d[k] + w[j]){
                res = min(res,w[j]);
            }
        }
        ans += res;
    }
    cout << ans << endl;
    return 0;
}