洛谷P1144最短路计数

题目描述

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

输入格式

第一行包含222个正整数N,MN,MN,M，为图的顶点数与边数。

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

输出格式

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

输入输出样例

输入 #1

输出 #1

1

1

1

2

4
跑一遍SPFA,松弛的时候顺便统计条数即可。注意要边加边模，开两倍边数组存储反向边。

#include <bits/stdc++.h>

#define MOD 100003

using namespace std;

int n,m;

const int N=,M=;//两倍存双向边

int head[N],ver[M],edge[M],Next[M],d[N][];//d[i][0]存储最短路距离 d[i][1]存储最短路径数目

int tot=;

queue<int>q;

bool v[N];

void add(int x,int y,int z)

{

    ver[++tot]=y;

    edge[tot]=z;

    Next[tot]=head[x];

    head[x]=tot;

}

void spfa()

{

    int i;

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

    {

        d[i][]=0x3f3f3f3f;

        d[i][]=;

    }

    memset(v,,sizeof(v));

    d[][]=;

    d[][]=;//一定要初始化为1，自己到自己有一条长为0的最短路

    v[]=;

    q.push();

    while(q.size())

    {

        int x=q.front();

        q.pop();

        v[x]=;

        for(i=head[x];i;i=Next[i])

        {

            int y=ver[i],z=edge[i];

            if(d[y][]>d[x][]+z)

            {

                d[y][]=d[x][]+z;

                d[y][]=d[x][];//能被更新的话直接继承过来

                if(!v[y])q.push(y),v[y]=;

            }

            else if(d[y][]==d[x][]+z)

            {

                d[y][]=(d[y][]+d[x][])%MOD;//相等的话再原来的基础上添加由x到y经过长为z的边的最短路径数目（即d[x]）

            }

        }

    }

}

int main()

{

    cin>>n>>m;

    int i;

    for(i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);//存无向图

        add(y,x,z);

    }

    spfa();

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

    {

        if(d[i][]!=0x3f3f3f3f)printf("%d\n",d[i][]%MOD);

        else printf("0\n");

    }

}

巴特西

洛谷P1144最短路计数

题目描述

输入格式

输出格式

输入输出样例

最新文章

热门文章