只会迪杰斯特拉

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f, kMOD = 1E5 + 3;
using P = pair<int, int>;
int n, m, u, v;

void dijkstra(vector<vector<int>>& g,
              vector<int>& seen,
              vector<int>& dists,
              vector<int>& counts) {

  priority_queue<P, vector<P>, greater<P>> pq;
  pq.emplace(0, 1);
  dists[1] = 0;
  counts[1] = 1;

  while (not pq.empty()) {
    const auto [d, u] = pq.top(); pq.pop();
    if (seen[u]) continue;
    seen[u] = 1;

    // 学名：松驰
    for (const auto& v : g[u]) {
      if (seen[v]) continue;
      if (d + 1 < dists[v]) {
        counts[v] = counts[u];
        dists[v] = d + 1;
        pq.emplace(d + 1, v);
      } else if (d + 1 == dists[v]) {
        counts[v] = (counts[v] + counts[u]) % kMOD;
      }
    } 
  }
}

// debug helper function
void printGraph(vector<vector<int>>& g) {
  for (int u = 1; u <= n; ++u) {
    printf("%d: [", u);
    for (const auto& x : g[u]) printf(" %d", x);
    printf("]\n");
  }
  putchar('\n');
}

int main(void) {
  cin >> n >> m;
  // printf("%d %d\n", n, m);
  vector<vector<int>> g(n + 1);
  vector<int> seen(n + 1);
  vector<int> dists(n + 1, INF);
  vector<int> counts(n + 1);
  while (m--) {
    cin >> u >> v;
    if (u == v) continue; // 自环边 (self edge)
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  // printGraph(g);
  dijkstra(g, seen, dists, counts);

  for (int i = 1; i <= n; ++i)
    printf("%d\n", counts[i]);

  return 0;
}