acwing.djikstra求最短路径1：https://www.acwing.com/problem/content/851/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 1; i < n; i ++) //循环n-1趟
    {
        //先找最小dist且未被遍历过的顶点
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        // 判断结点是否合理,INF代表无未遍历过且联通的结点了
        // 这也是为什么t初始化不为1,因为1可能被遍历过了
        if(dist[t] == INF) 
            return ;

        // 出栈时访问结点
        st[t] = true; 

        //更新新加入的结点t相邻的dist
        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    dijkstra();

    if(dist[n] == INF) cout << -1;
    else cout << dist[n];
    return 0;
}

acwing.dijkstra求最短路2：https://www.acwing.com/problem/content/852/

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

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5;

int n, m;
int d[N];
bool st[N];

struct Node
{
    int id;
    int w;
    Node *next;
    Node(int _id, int _w):id(_id), w(_w), next(NULL){}
} *head[N];

void add(int a, int b, int w)
{
    Node *p = new Node(b, w);
    p ->next = head[a];
    head[a] = p;
}

void dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); // heap按照key排序

    // 这里不循环n次的原因是因为：
    // 每次从heap中找到的最小值可能不符合未访问过的条件
    // 可能需要多次从heap中取出最小值
    while(heap.size())
    {
        PII pii = heap.top();
        heap.pop();
        int t = pii.second;

        if(st[t]) continue;

        st[t] = true;

        for(Node *p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if(d[j] > d[t] + p->w)
            {
                d[j] = d[t] + p->w;
                heap.push({d[j], j});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }

    dijkstra();

    if(d[n] == 0x3f3f3f3f) puts("-1");
    else
        cout << d[n];

    return 0;
}

dijkstra求路径

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];
int path[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    path[1] = -1;

    for(int i = 1; i < n; i ++) //循环n-1趟
    {
        //先找最小dist且未被遍历过的顶点
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        // 判断结点是否合理,INF代表无未遍历过且联通的结点了
        // 这也是为什么t初始化不为1,因为1可能被遍历过了
        if(dist[t] == INF) 
            return ;

        // 出栈时访问结点
        st[t] = true; 

        //更新新加入的结点t相邻的dist
        for(int j = 1; j <= n; j ++)
        {
            if(dist[j] >dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
                path[j] = t;
            }
        }

    }
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    dijkstra();

    if(dist[n] == INF) cout << -1;
    else 
        for(int i = n; i != -1; i = path[i])
            cout << path[i] << " ";  //这里输出的是逆序的路径
    return 0;
}