标题没有打错没有打错没有打错
真·最短路计数和标签"最短路计数"
NOIp2017 逛公园 弱化
P1608 路径统计
在跑spfa的同时记录一个tot数组统计路径条数
如果搜到的点到起点的距离等于当前点到起点的距离加上这两点间的那条边的距离，那么就将搜到的点的路径数加上当前点的路径数
1 if(dis[i]==dis[k]+w) 2 tot[i]+=tot[k];
如果更新了搜索到的点到起点的最短距离，那么将到达改点的路径数改为当前点的路径数
1 if(dis[i]>dis[k]+w){ 2 dis[i]=dis[k]+w; 3 tot[i]=tot[k]; 4 }
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int maxn=2e3+10; 6 inline int read(){ 7 int x=0,f=1; 8 char c=getchar(); 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 10 while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();} 11 return x*f; 12 } 13 int n,m,fl; 14 struct edge{ 15 int u,v,w,nxt; 16 }e[maxn*maxn]; 17 int head[maxn],cnt,d[maxn],v[maxn],tot[maxn]; 18 int vis[maxn][maxn]; 19 inline void add(int u,int v,int w){ 20 e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w; 21 e[cnt].nxt=head[u];head[u]=cnt; 22 } 23 void spfa(){ 24 memset(d,0x3f,sizeof(d)); 25 queue<int>q; 26 q.push(1);d[1]=0;v[1]=1;tot[1]=1; 27 while(!q.empty()){ 28 int x=q.front();q.pop(); 29 for(int i=head[x];i;i=e[i].nxt){ 30 int y=e[i].v,w=e[i].w; 31 if(d[y]>d[x]+w){ 32 d[y]=d[x]+w;tot[y]=tot[x]; 33 if(!v[y]&&tot[x]){ 34 q.push(y);v[y]=1; 35 } 36 } 37 else if(d[y]==d[x]+w)tot[y]+=tot[x]; 38 } 39 } 40 } 41 int main(){ 42 n=read();m=read(); 43 if(m==0){ 44 puts("No answer");return 0; 45 } 46 for(int i=1;i<=m;i++){ 47 int u=read(),v=read(),w=read(); 48 if(!vis[u][v]||vis[u][v]>w){ 49 add(u,v,w);vis[u][v]=w; 50 if(v==n)fl++; 51 } 52 } 53 spfa(); 54 if(fl==1)tot[n]++; 55 if(d[n]!=0x3f)printf("%d %d",d[n],tot[n]); 56 else puts("No answer"); 57 return 0; 58 } 59 } 60 signed main(){ 61 gengyf::main(); 62 return 0; 63 }
一些坑！！！
单向边！n点入度为1！没有边！
心路历程
P1144 最短路计数
路径统计弱化版
不需要判重边
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int mod=1e5+3; 6 const int maxn=2e6+10; 7 inline int read(){ 8 int x=0,f=1; 9 char c=getchar(); 10 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 11 while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();} 12 return x*f; 13 } 14 int n,m,fl; 15 struct edge{ 16 int u,v,w,nxt; 17 }e[maxn]; 18 int head[maxn],cnt,d[maxn],v[maxn],tot[maxn]; 19 inline void add(int u,int v,int w){ 20 e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w; 21 e[cnt].nxt=head[u];head[u]=cnt; 22 } 23 void spfa(){ 24 memset(d,0x3f,sizeof(d)); 25 queue<int>q; 26 q.push(1);d[1]=0;v[1]=1;tot[1]=1; 27 while(!q.empty()){ 28 int x=q.front();q.pop(); 29 for(int i=head[x];i;i=e[i].nxt){ 30 int y=e[i].v,w=e[i].w; 31 if(d[y]>d[x]+w){ 32 d[y]=d[x]+w;tot[y]=tot[x]%mod; 33 if(!v[y]&&tot[x]){ 34 q.push(y);v[y]=1; 35 } 36 } 37 else if(d[y]==d[x]+w)tot[y]+=tot[x],tot[y]%=mod; 38 } 39 } 40 } 41 int main(){ 42 n=read();m=read(); 43 for(int i=1;i<=m;i++){ 44 int u=read(),v=read(); 45 add(u,v,1);add(v,u,1); 46 } 47 spfa(); 48 for(int i=1;i<=n;i++){ 49 printf("%d ",tot[i]); 50 } 51 return 0; 52 } 53 } 54 signed main(){ 55 gengyf::main(); 56 return 0; 57 }