最短路计数

AK-ls 2019-08-28 原文

题目描述

给出一个

输入格式

第一行包含

接下来

输出格式

共

一道简单题，用SPFA去更新最短路，每次更新时，即dis[y] > dis[x] + v, 点y的最短路就等于点x的最短路，而当dis[y] = dis[x] + v时，就说明该点产生了第二条最短路，即点y最短路的条数加上点x最短路的条数。即使当前不是最短路，但是当更新到最短路时，该最短路条数数组会重置成此时点x的最短路条数，所以这个算法是正确的。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e6 + 100;
const int MAXM = 3e3 + 10;

template < typename T > inline void read(T &x) {
    x = 0; T ff = 1, ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') ff = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *=ff;
}

template < typename T > inline void write(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
 
int n, m;
int dis[MAXN], vis[MAXN], a[MAXN]; 
int lin[MAXN], tot = 0;
struct edge {
    int y, next;
}e[MAXN];

inline void add(int xx, int yy) {
    e[++tot].y = yy;
    e[tot].next = lin[xx];
    lin[xx] = tot;
}

inline void SPFA() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    queue < int > q; 
    dis[1] = 0; a[1] = 1;
    q.push(1);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        vis[x] = false;
        for(int i = lin[x], y; i; i = e[i].next) {
            if(dis[y = e[i].y] > dis[x] + 1) {
                dis[y] = dis[x] + 1;
                a[y] = a[x]; 
                if(!vis[y]) {
                    vis[y] = true;
                    q.push(y);
                }
            }
            else if(dis[y] == dis[x] + 1) {
                a[y] += a[x];
                a[y] %= 100003;
            }
        }
    }
}

int main() {
    read(n); read(m);
    for(int i = 1; i <= m; ++i) {
        int u, v;
        read(u); read(v);
        if(u == v) continue;
        add(u, v);
        add(v, u);
    }
    SPFA();
    for(int i = 1; i <= n; ++i) {
        write(a[i]);
        puts("");
    }
    return 0;
}