单源最短路模板

SPFA

#include <bits/stdc++.h>

#define rint register int
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int inf = 1e9;

int h[N], e[M], ne[M], dist[N], w[M];
int n, m, s, idx;

queue<int> q;
bool v[N];

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

void SPFA()
{
    memset(dist, 0x3f, sizeof dist);
    memset(v, 0, sizeof v);
    dist[s] = 0;
    v[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        v[x] = false;
        for (rint i = h[x]; i; i = ne[i])
        {
            int y = e[i];
            int z = w[i];
            if (dist[y] > dist[x] + z)
            {
                dist[y] = dist[x] + z;
                if (!v[y])
                {
                    q.push(y);
                    v[y] = true;
                }
            }
        }
    }
}

signed main()
{
    cin >> n >> m >> s;
    
    for (rint i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    SPFA();

    for (rint i = 1; i <= n; i++)
    {
        /*if (dist[i] == 0x3f3f3f3f)
        {
            cout << 2147483647 << " ";
            continue;
        }*/
        cout << dist[i] << " ";
    }

    return 0;
}

dijkstra

#include <bits/stdc++.h>

#define rint register int
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 1e6 + 5;

int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool v[N];
int n, m, s = 1, t;

std::priority_queue<std::pair<int, int> > q;

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

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    memset(v, 0, sizeof v);
    dist[s] = 0;
    q.push(std::make_pair(0, s));
    while (!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (v[x])
        {
            continue;
        }
        v[x] = 1;
        for (rint i = h[x]; i; i = ne[i])
        {
            int y = e[i];
            int z = w[i];
            if (dist[y] > dist[x] + z)
            {
                dist[y] = dist[x] + z;
                q.push(std::make_pair(-dist[y], y));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    
    for (rint i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    dijkstra();
    
    printf("%d", dist[n]);
    
    return 0;
}