题目大意： 在一个无向无权图中，求出点1到1~N点的最短路的数量。
题解： spfa+队列优化： ans[i]表示有多少条1到i点的最短路。 双向图，要把2个相连的点正反方向都存储。 做一个spfa，如果dis[s[i]]+1小于当前的dis[t[i]]就替换，并且ans[t[i]]就等于ans[s[i]]的数量，如果等于把ans[t[i]]跟ans[s[i]]合并。 最后输出就好了，不过要注意取模。
var list,s,t,next,p:array [0..4000001] of longint; dis,ans:array [0..1000001] of longint; v:array [0..1000001] of boolean; x,i,j,n,m,g:longint; procedure spfa; var head,tail,i:longint; begin head:=0; tail:=1; dis[1]:=0; ans[1]:=1; v[1]:=true; p[1]:=1; while head<tail do begin inc(head); i:=list[p[head]]; while i>0 do begin if dis[s[i]]+1=dis[t[i]] then ans[t[i]]:=(ans[t[i]]+ans[s[i]]) mod 100003; if dis[s[i]]+1<dis[t[i]] then begin dis[t[i]]:=dis[s[i]]+1; if v[t[i]]=false then begin v[t[i]]:=true; inc(tail); p[tail]:=t[i]; end; ans[t[i]]:=ans[s[i]]; end; i:=next[i]; end; v[p[head]]:=false; end; end; begin readln(n,g); for i:=1 to g do begin inc(m); readln(s[m],t[m]); next[m]:=list[s[m]]; list[s[m]]:=m; inc(m); s[m]:=t[m-1]; t[m]:=s[m-1]; next[m]:=list[s[m]]; list[s[m]]:=m; end; for i:=1 to n do begin dis[i]:=maxlongint; v[i]:=false; end; spfa; for i:=1 to n do writeln(ans[i]); end.