洛谷P1144 最短路计数
图论最短路 记忆化搜索
题意 求 起点 到各个点的最短路 有几条
注意 要 %
最短路计数
首先求一遍单源最短路 可以用 SPFA 或者 堆优化 + dijkstra
然后就可以求 每个点 到 1 的最短距离
然后 记忆化搜索下去 就可以求得 到这一个点的最短路有几条
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <string> 6 #include <algorithm> 7 #include <iomanip> 8 #include <iostream> 9 #include <queue> 10 using namespace std ; 11 12 const int maxn = 1000011,maxe = 2000011,inf = 1e9 ; 13 struct node{ 14 int to,pre ; 15 }; 16 node e[2*maxe] ; 17 int n,m,cnt,u,v,x,y,ans ; 18 int dist[maxn],head[maxn],dp[maxn] ; 19 bool vis[maxn],f[maxn] ; 20 queue <int> Q ; 21 22 inline void adde(int x,int y) 23 { 24 e[++cnt].to = y ; 25 e[cnt].pre = head[ x ] ; 26 head[ x ] = cnt ; 27 } 28 29 inline void SPFA(int s,int t) 30 { 31 for(int i=1;i<=n;i++) dist[ i ] = inf,vis[ i ] = 0 ; 32 Q.push(s) ; 33 vis[ s ] = 1 ; 34 dist[ s ] = 0 ; 35 while(!Q.empty()) 36 { 37 u = Q.front() ; 38 vis[ u ] = 0 ; 39 Q.pop() ; 40 for(int i=head[ u ];i;i = e[ i ].pre) 41 { 42 v = e[ i ].to ; 43 if( dist[ u ] + 1 < dist[ v ] ) 44 { 45 dist[ v ] = dist[ u ]+1 ; 46 if(!vis[ v ]) 47 { 48 vis[ v ] = 1; 49 Q.push(v) ; 50 } 51 } 52 } 53 } 54 } 55 56 int dfs(int u) // 记忆化搜索 57 { 58 int v ; 59 if(dp[ u ]) return dp[ u ] ; // 60 for(int i=head[ u ];i;i=e[i].pre) 61 { 62 v = e[ i ].to ; 63 if(dist[v]+1==dist[ u ]) dp[ u ] = (dp[ u ]+dfs(v)) % 100003 ; 64 } 65 return dp[ u ] ; 66 } 67 68 int main() 69 { 70 scanf("%d%d",&n,&m) ; 71 for(int i=1;i<=m;i++) 72 { 73 scanf("%d%d",&x,&y) ; 74 adde(x,y) ; 75 adde(y,x) ; 76 } 77 SPFA(1,n) ; 78 dp[ 1 ] = 1 ; 79 80 for(int i=1;i<=n;i++) 81 printf("%d ",dfs( i ) ) ; 82 return 0 ; 83 }