这道题先跑一个最短路, 然后在用记忆化搜索搜出最短路条数.
开一个 \(dis\) 数组存最短路长度, 开一个 \(ans\) 数组存答案.
搜到一个节点 \(v\), 寻找它能到达的每个节点 \(u\), 如果 \(dis[u]+1==dis[v]\), 说明用最短路的走法走到 \(u\) 后, 直接走到 \(v\) 就都是 \(1\) 到 \(v\) 的一条合法最短路.
此时,\(ans[v]=ans[u]+ans[v]\).
写记忆化搜索的时候, 不要算过了还递归进去再返回, 那样会 TLE.
此外, 把记忆化放进输出是一个很巧的方法.
- #include<bits/stdc++.h>
- #define N 1000010
- #define M 2000010
- #define MOD 100003
- #define INF 0x3f3f3f3f
- using namespace std;
- int n,m,cnt;
- int head[M],dis[N],ans[N];
- bool vis[N];
- struct node {
- int nxt,to;
- }e[M*2];
- void addEdge(int u,int v) {
- e[++cnt]=(node){head[u],v};
- head[u]=cnt;
- return;
- }
- void Read() {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- addEdge(x,y);
- addEdge(y,x);
- }
- return;
- }
- void Init() {
- for(int i=2;i<=n;i++) {
- dis[i]=INF;
- }
- return;
- }
- void SPFA() {
- queue <int> q;
- ans[1]=1;
- q.push(1);
- while(!q.empty()) {
- int u=q.front();
- q.pop();
- for(int i=head[u];i;i=e[i].nxt) {
- int v=e[i].to;
- if(dis[u]+1<dis[v]) {
- dis[v]=dis[u]+1;
- q.push(v);
- }
- }
- }
- return;
- }
- int Calc(int x) {
- for(int i=head[x];i;i=e[i].nxt) {
- int u=e[i].to;
- if(dis[u]+1==dis[x]) {
- ans[u]?ans[x]=(ans[x]+ans[u])%MOD:ans[x]=(ans[x]+Calc(u))%MOD;
- }
- }
- return ans[x];
- }
- void Print() {
- for(int i=1;i<=n;i++) {
- printf("%d\n",ans[i]?ans[i]:Calc(i));
- }
- return;
- }
- int main()
- {
- Read();
- Init();
- SPFA();
- Print();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3232791.html