洛谷P1144最短路计数

Dijkstra解法

#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define MAX_N 1000005
#define MAX_M 2000005

int n, m;

int cnt_dis[MAX_N], dis[MAX_N];
 
int head[MAX_N], to[MAX_M << 1], ne[MAX_M << 1], cnt_edge;

inline void add_edge(int a, int b) {
    to[++cnt_edge] = b;
    ne[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return ;
}
struct Node {
    int e, dis;
    bool operator< (const Node& a) const {
        return dis > a.dis;
    }
};
const int mod = 100003;
inline void func(int u) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue <Node> q;
    q.push((Node){u, 0});
    cnt_dis[u] = 1;
    dis[u] = 0;
    while (!q.empty()) {
        Node tp = q.top();
        q.pop();
        if (dis[tp.e] < tp.dis) continue;
        for (int i = head[tp.e]; i; i = ne[i]) {
            if (dis[to[i]] < tp.dis + 1) continue;
            else if (dis[to[i]] == tp.dis + 1) {
                cnt_dis[to[i]] += cnt_dis[tp.e];
                cnt_dis[to[i]] %= mod;
            } else {
                dis[to[i]] = tp.dis + 1;
                cnt_dis[to[i]] = cnt_dis[tp.e];
                q.push((Node){to[i], dis[to[i]]});
            }
            
        }
    }
}


int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int a, b;
        a = read(), b = read();
        add_edge(a, b);
        add_edge(b, a);
    }
    func(1);
    for (int i = 1; i <= n; i++) printf("%d\n", cnt_dis[i]);
    return 0;
}

SPFA解法

#include <stdio.h>

inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define MAX_N 1000005
#define MAX_M 2000005

int n, m;

int cnt_dis[MAX_N], dis[MAX_N];
 
int head[MAX_N], to[MAX_M << 1], ne[MAX_M << 1], cnt_edge;

inline void add_edge(int a, int b) {
    to[++cnt_edge] = b;
    ne[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return ;
}

const int mod = 100003;
int q[MAX_M], vis[MAX_N], l, r;
#include <string.h>

inline void SPFA(int u) {
    memset(dis, 0x3f, sizeof(dis));
    q[0] = u;
    vis[u] = 1;
    dis[u] = 0;
    r = 1;
    cnt_dis[u] = 1;
    while (l < r) {
        int tp = q[l++];
        vis[tp] = 0;
        for (int i = head[tp]; i; i = ne[i]) {
            if (dis[to[i]] < dis[tp] + 1) continue;
            else if (dis[to[i]] == dis[tp] + 1) {
                cnt_dis[to[i]] += cnt_dis[tp];
                cnt_dis[to[i]] %= mod;
            } else {
                dis[to[i]] = dis[tp] + 1;
                cnt_dis[to[i]] = cnt_dis[tp];
                q[r++] = to[i];
                vis[to[i]] = 1;
            }
        }
    } 
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int a, b;
        a = read(), b = read();
        add_edge(a, b);
        add_edge(b, a);
    }
    SPFA(1);
    for (int i = 1; i <= n; i++) printf("%d\n", cnt_dis[i]);
    return 0;
}