最短路计数（SPFA× Dijkstra√）

题目描述

给出一个n个顶点m条边的无向无权图，顶点编号为1−n。问从顶点1开始，到其他每个点的最短路有几条。

输入格式

第一行包含2个正整数n，m，为图的顶点数与边数。

接下来M行，每行2个正整数x,y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。

输出格式

共N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出ans mod 100003后的结果即可。如果无法到达顶点i则输出0。

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

（补更~）虽然SPFA过了边权为1的数据，但今天机房某位大佬出了一个边权不为1的数据，卡掉了SPFA，然后我就知道要用Dijkstra算法，具体SPFA算法为什么被卡我也不是很知道。

被卡数据如下：

4 4
1 2 2
2 3 1
1 3 3
3 4 1

代码已更新：

#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, v, next;

}e[MAXN];

inline void add(int xx, int yy, int vv) {

    e[++tot].y = yy;

    e[tot].v = vv;

    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;

            }

        }

    }

}*/

inline void Dijkstra() {

    memset(dis, 0x3f, sizeof(dis));

    memset(vis, false, sizeof(vis));

    priority_queue < pair < int, int > > q;

    q.push(make_pair(0, 1));

    dis[1] = 0;

    a[1] = 1;

    while(!q.empty()) {

        int x = q.top().second;

        q.pop();

        if(vis[x]) continue;

        for(int i = lin[x], y; i; i = e[i].next) {

            if(dis[y = e[i].y] == dis[x] + e[i].v) a[y] = (a[y] + a[x]) % 100003;

            else if(dis[y] > dis[x] + e[i].v) {

                a[y] = a[x];

                dis[y] = dis[x] + e[i].v;

                q.push(make_pair(-dis[y], y));

            }

        }

    }

}

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, 1);

        add(v, u, 1);

    }

    Dijkstra();

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

        write(a[i]);

        puts("");

    }

    return 0;

}

巴特西

最短路计数（SPFA× Dijkstra√）

题目描述

输入格式

输出格式

最新文章

热门文章