Dijkstra（最短路模版）

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define MAX 0x3f3f3f3

int mp[105][105];          //两者之间的距离
int dis[105];              //起始点到其它点的最短路程
int biaoji[105];           //标记一个点是否是旧点
int weizhi;                //对到达的点进行位置标记

void Dijkstra(int m)
{
    biaoji[1]=1;             //将初始点标记
    for (int i=1;i<=m;i++)   //记录一开始初始点到各个点的距离
    {
        dis[i]=mp[1][i];
    }
    for (int i=1;i<=m;i++)
    {
        int minx=MAX;
        for (int j=1;j<=m;j++)
        {
            if( dis[j]<minx && biaoji[j]==0 )  //只要还有新点便进行更新 （重要） -》 我们找的新点是（所有点中 未被标记 且 距离初始点最近 的点）
            {
                minx=dis[j];
                weizhi=j;
            }
        }
        if(minx==MAX) break; //如果距离初始点的距离都为MAX，也就是没有点可以更新，就break；
        biaoji[weizhi]=1;
        for (int j=1;j<=m;j++)   //只要一个点经过标记点到初始点的距离可以更新，便更新。
        {
            if(biaoji[j]==0 && dis[j] > (dis[weizhi])+ mp[weizhi][j])
            {
                dis[j]=mp[weizhi][j] + dis[weizhi];
            }
        }
    }
}

int main ()
{
    int m,n,a,b,c;
    while (cin >> m >> n) //m表示点数，n表示边数
    {
        if(m==0&&n==0)break;
        memset(biaoji, 0, sizeof(biaoji));  //初始化

        for (int i=1;i<=105;i++) //将两个点之间的距离都设为最大值
        {
            for (int j=1;j<=105;j++)
            {
                mp[i][j]=MAX;
            }
        }
        for (int i=1;i<=n;i++) //遍历n条边，将两个端点之间的距离更新
        {
            cin >> a >> b >> c;
            mp[a][b]=mp[b][a]=c;
        }
        Dijkstra(m);
        cout << dis[m] << endl;
    }
    return 0;
}

堆优化
//Dijkstra的堆优化
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
#define N 200005
#define MAX 0x3f3f3f3f3f3f3f3f

ll head[N],cnt;
struct sss{
    ll v,w,next;
}edge[N << 1];

struct node{
    ll id,dis;
    bool operator <(const node &a) const {
        return dis > a.dis; //从小到大排序
    }
};

void add_edge(ll u,ll v,ll w){
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

ll n,m,a,b,c,weizhi;
ll vis[N];   //标记数组
ll dis[N];   //初始点 - 终点 的距离

void Dijkstra(){
    dis[1] = 0;
    priority_queue<node>q;
    q.push(node{1,0});
    while (!q.empty()) {
        node o = q.top(); //用优先队列直接找出距离最短的点
        q.pop();
        ll weizhi = o.id;
        if(vis[weizhi]==1) continue;
        vis[weizhi] = 1;
        for (ll i=head[weizhi] ; i!=-1 ; i=edge[i].next){ //遍历与i的每一条边
            ll j = edge[i].v;
            if(vis[j] == 1) continue;
            if(dis[j] > dis[weizhi] + edge[i].w){
                dis[j] = dis[weizhi] + edge[i].w;
                q.push(node{j,dis[j]});
            }
        }
    }
}

void init(){
    memset(vis, 0, sizeof(vis));
    for(int i=1;i<=n;i++)dis[i]=MAX;
//    memset(dis, MAX, sizeof(dis));
    memset(head, -1, sizeof(head));
    cnt = 0;
    for (int i=1;i<=m;i++){
        cin >> a >> b >> c;
        add_edge(a, b, c);
        add_edge(b, a, c);
    }
}

int main()
{
    cin >> n >> m;
    init();
    Dijkstra();
    if(dis[n] == MAX) cout << "qwb baka" << endl;
    else cout << dis[n] << endl;
    return 0;
}