单源最短路

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2510;

#define INF 0x3f3f3f3f

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

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    for (int i = 1; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return dist[T];
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &T);
    memset(g, 0x3f, sizeof g);

    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());
    return 0;
}

Til the Cows Come Home

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

#define INF 0x3f3f3f3f

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

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

    for (int i = 1; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return dist[n];
}

int main() {
    scanf("%d%d", &m, &n);
    memset(g, 0x3f, sizeof g);

    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());
    return 0;
}

最短路计数

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

using namespace std;

const int N = 2000010;

#define mo 100003
#define INF 0x3f3f3f3f

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
int ans[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);
    dist[1] = 0;
    ans[1] = 1;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {

            int j = e[i];

            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                ans[j] = ans[t];

                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            } else if (dist[j] == dist[t] + w[i])
                ans[j] = (ans[t] + ans[j]) % mo;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    idx = 0;

    while (m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b, 1);
        add(b, a, 1);
    }

    spfa();

    for (int i = 1; i <= n; i ++ )

        if (dist[i] == INF)
            puts("0");
        else
            printf("%d\n", ans[i]);

    return 0;
}