题解 P1144 【最短路计数】

· · 题解

算是一道比较裸的最短路，使用SPFA即可

注意取模

使用t数组保存每个节点最短路的数量

易知当某节点第一次被访问时，此时t[father]+1即为该节点最短路，此后若再访问到该点，必有t[new_father]+1>=t[father]+1

这个题用邻接表存储，为了省点空间，我用的指针式链表，权当练练指针的使用，想用指针链表的可以看看

代码中debug_out子程序只是调试用的

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
#define M 100003
#define N 1000010
using namespace std;
struct node{
    node* next;
    int data;
    node(int x=INF){
        data=x;
        next=NULL;
    }
};
node p[N];
int t[N];
int n,m;
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        node *a=p[x].next;
        p[x].next=new node(y);
        p[x].next->next=a;
        //========================
        node *b=p[y].next;
        p[y].next=new node(x);
        p[y].next->next=b;
    }
}
void suan(){
    memset(t,0,sizeof(t));
    p[1].data=0,t[1]=1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(node* k=p[x].next;k!=NULL;k=k->next){
            if(t[k->data]==0){
                t[k->data]+=t[x];
                p[k->data].data=p[x].data+1;
                q.push(k->data);
            }
            else if(p[k->data].data==p[x].data+1){
                t[k->data]+=t[x];
                t[k->data]%=M;
            }
        }
    }
}
void debug_out(){
    for(int i=1;i<=n;i++){
        printf("%d:",i);
        if(p[i].next!=NULL){
            node* k=p[i].next;
            while(true){
                printf("%d ",k->data);
                if(k->next==NULL)break;
                k=k->next;
            }
        }
        printf("\n");
    }
}
int main(){
    init();
    suan();
    //debug_out();
    for(int i=1;i<=n;i++){
        printf("%d\n",t[i]);
    }
    //system("pause");
    return 0;
}