(로곡1144) 최단거리 계수 #spfa#

15267 단어 최단 경로

제목.


최단로의 개수를 구하다

분석하다.


spfa로 답을 구하고, 디스가 느슨한 상태에서 동시에 답을 구한다.

코드

#include 
using namespace std;
struct q{
    int x,y,w,next;
}a[2000001]; int go=0;
int n,m,l,d[1000001],ans[1000001],t,list[1000001],ls[1000001];
bool v[1000001];
void spfa(int st){
    int head=0,tail=1;
    for (int i=1;i<=n;i++) d[i]=2147483647;
    list[1]=st; v[st]=ans[st]=1; d[st]=0;
    do{
        head++;
        if (head>n) head=1;
        t=ls[list[head]];
        while (t>0){
            if (d[a[t].x]+1<d[a[t].y]){
                d[a[t].y]=d[a[t].x]+1;
                ans[a[t].y]=ans[a[t].x];//       
                if (!v[a[t].y]){
                    v[a[t].y]=1;
                    tail++;
                    if (tail>n) tail=1;
                    list[tail]=a[t].y;
                }
            }//       ,     =        
            else if (d[a[t].x]+1==d[a[t].y])
            ans[a[t].y]=(ans[a[t].y]+ans[a[t].x])%100003;//            ,           
            t=a[t].next;
        }
        v[list[head]]=0;
    }while (head!=tail);//     bug
    for (int i=1;i<=n;i++) printf("%d
"
,ans[i]); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); a[++go].x=u; a[go].y=v; a[go].next=ls[u]; ls[u]=go; a[++go].x=v; a[go].y=u; a[go].next=ls[v]; ls[v]=go; } spfa(1); }

좋은 웹페이지 즐겨찾기