很早之前就已经了解过最短路算法了，这里写几个优化后的模板以便复习

Dijkstra堆优化+链式前向星

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+5;
const int inf = 0x3f3f3f3f;
int head[maxn],cnt,dis[maxn];//head[i]记录点i最后出现的位置 
int n,m;
bool vis[maxn];
struct edge{
    int to,w,next;
}e[maxn];


struct node{
    int u,w;
    node(int uu,int ww):u(uu),w(ww){}
    bool operator <(const node &r)const{
        return w > r.w;
    }
};

void add_edge(int u,int v,int w){
    e[cnt].next = head[u];
    e[cnt].to = v;
    e[cnt].w = w;
    head[u] = cnt++;
}

//链式前向星 
void dij(int st ,int ed){
    memset(dis,inf,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[st] = 0; 
    for(int i = 1 ; i <= n ; i++){
        int u = -1,minn = inf;
        for(int j = 1 ; j <= n ; j++){

            if(vis[j] == false && vis[j] < minn){
                minn = vis[j];
                u = j;
            }
        }
        if(u == -1) break;
        vis[u] = true;
        for(int j = head[u] ; j != -1 ; j = e[j].next){
            int v = e[j].to,w = e[j].w;
            if(vis[v] == false && dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
            }
        } 
    }
    if(dis[ed] == inf) cout << "-1" << endl;
    else cout << dis[ed] << endl;
}
//链式前向星+堆优化 
void dij2(int st,int ed){
    memset(vis,false,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    dis[st] = 0;
    priority_queue<node>pque;
    pque.push(node(st,0));
    while(!pque.empty()){
        node t = pque.top();
        pque.pop();
        int u = t.u;
        if(vis[u])continue;
        vis[u] = true;
        for(int i = head[u] ; i != -1 ; i = e[i].next){
            int v = e[i].to,w = e[i].w;
            if(vis[v] == false && dis[v] > dis[u] + w){
                dis[v] = dis[u]+w;
                pque.push(node(v,dis[v]));
            }
        }
    }
    if(dis[ed] != inf) cout << dis[ed] << endl;
    else cout << "-1" << endl; 
}


int main(){
    memset(head,-1,sizeof(head));

    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int u,v,w;
        cin >> u >> v >> w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    dij(1,n); 
    dij2(1,n);
    return 0;
}

Spfa队列优化+链式前向星

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e4+5;
const int inf = 0x3f3f3f3f;
int cnt,n,m,head[maxn],dis[maxn];
bool vis[maxn];
struct edge{
    int to,w,next;
}e[maxn];


void add_edge(int u,int v,int w){
    e[cnt].next = head[u];
    e[cnt].w = w;
    e[cnt].to = v;
    head[u] = cnt++;
}

void spfa(int st,int ed){
    memset(vis,false,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    queue<int>q;
    q.push(st);
    dis[st] = 0,vis[st] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = head[u] ; i != -1 ; i = e[i].next){
            int v = e[i].to,w = e[i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                    q.push(v);
                    vis[u] = true;
                }
            }
        }
        vis[u] = false;

    }
    cout << dis[ed] << endl;
}



int main(){
    memset(head,-1,sizeof(head));
    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int u,v,w;
        cin >> u >> v >> w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    spfa(1,n);
    return 0;
}

Floyed算法

暴力算法，三重for循环，最外层表示转折点，次外层表示起点，内层表示终点