只A了最后一个测试点,参照了题解也没找出来···
#include <bits/stdc++.h>
using namespace std;
const int N=2000005;
const int mod=100003;
long long n,m,dis[N],last[N],cnt[N];
bool mark[N];
struct qwe{
int x,y,next;
};qwe e[N];
struct awa{
int op;
long long dis;
awa(int op_,long long dis_){
op=op_;
dis=dis_;
}
};
priority_queue<awa> pq;
bool operator <(awa a,awa b){
return a.dis>b.dis;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1,j=1; i<=m; i++){
int x,y;
scanf("%d%d",&x,&y);
e[j].x=x;
e[j].y=y;
e[j].next=last[x];
last[x]=j;
j++;
e[j].x=y;
e[j].y=x;
e[j].next=last[x];
last[x]=j;
j++;
}
for(int i=1; i<=n; i++){
dis[i]=1e20;
mark[i]=0;
}
pq.push(awa(1,0));
dis[1]=0;
cnt[1]=1;
while(!pq.empty()){
int kl=pq.top().op;
pq.pop();
if(mark[kl]==1){
continue;
}
mark[kl]=1;
for(int i=last[kl]; i; i=e[i].next){
int g=e[i].y;
if(dis[g]==dis[kl]+e[i].x){
cnt[g]=(cnt[g]+cnt[kl])%mod;
}
if(dis[g]>dis[kl]+e[i].x){
dis[g]=dis[kl]+e[i].x;
cnt[g]=cnt[kl];
pq.push(awa(g,dis[g]));
}
}
}
for(int i=1; i<=n; i++){
cout<<cnt[i]<<endl;
}
return 0;
}