#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>

using namespace std;


typedef pair<int, int> PII;
const int N = 150010; // 


int n,m;
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
int st[N]; // 如果为true说明这个点的最短路径已经确定

priority_queue<PII, vector<PII>, greater<PII>> heap;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int djk(int start,int end)
{
    memset(dist,0x3f,sizeof dist);
    dist[start]=0;
    //st[1]=1;
    heap.push({0,start});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver =t.second;
        int 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(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});
            }

        }

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

    return dist[end];

}




int main()
{
    int start,end;
    cin>>n>>m>>start>>end;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int res=djk(start,end);
    cout<<res;
    return 0;
}

二刷，简单堆优化djk，目前掌握应该没什么问题了

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

using namespace std;
const int N=3000,M=200010;

int st[N],h[N],e[M],ne[M],w[M],idx;
int dist[N];
int n,m,start,en;
typedef pair<int,int> pii;

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

int djk()
{
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.push({0,start});
    dist[start]=0;
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second;
        int 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(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});
            }
        }

    }

    return dist[en];
}

int main()
{
    cin>>n>>m>>start>>en;
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cout<<djk();
    return 0;
}

2023/12/2

堆优化djk， 没什么问题

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>

using namespace std;


typedef pair<int, int> PII;
const int N = 150010; // 


int n,m;
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
int st[N]; // 如果为true说明这个点的最短路径已经确定

priority_queue<PII, vector<PII>, greater<PII>> heap;

int start, en;

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

int main()
{
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));

    cin>>n>>m>>start>>en;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    heap.push({0, start});
    dist[start] = 0;

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int v=t.second;
        int d=t.first;

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

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

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

        }
    }

    cout<<dist[en]<<endl;


    return 0;
}