这道题 一道有关于最短路的图论问题。 要求从1开始求解最短路的条数。
这个题十分有趣，首先，跑裸的spfa（或者dijkstra）算出从1开始的最短路的长度。
再其次，计数的话，可以用记忆化搜索（相当于DAG dp）我们现在所遍历的路径长度要刚好是最短路的长度。
（这个程序中会有体现的）
这个题我前面一直在TLE，就是没有用记忆化，暴力去找路径。（第一遍还因为没算空间MLE。。TAT）
后来优化后 时间效率挺不错。（300多ms）
下面上代码：
#include <bits/stdc++.h>
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, l, r) for(int i = (l); i <= (int)(r); ++i)
#define Fordown(i, r, l) for(int i = (r); i >= (int)(l); --i)
using namespace std; inline int read(){
int x = , fh = ; char ch;
for(; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -;
for(; isdigit(ch); ch = getchar()) x = (x<<) + (x<<) + (ch^'');
return x * fh;
} const int N = , M = << , inf = 0x3f3f3f3f;
const int mod = ; struct graph {
int to[M], Head[N], Next[M], val[M], e;
void init() {
e = ;
Set(Head, );
}
void add_edge (int u, int v, int w) {
to[++e] = v;
val[e] = w;
Next[e] = Head[u];
Head[u] = e;
}
};
graph G;
#define Travel(i, u, G) for(int i = G.Head[u]; i; i = G.Next[i])
//链式前向星的存图方式，Travel是遍历，这样便于我们写多图，而且挺方便的
bool inq[N];
int dis[N];
void spfa() {
queue<int> Q;
Set(dis, inf);
Q.push(); dis[] = ;
while (!Q.empty() ) {
int now = Q.front(); Q.pop();
inq[now] = false;
Travel(i, now, G) {
int v = G.to[i];
if (dis[v] > dis[now] + G.val[i]) {
dis[v] = dis[now] + G.val[i];
if (!inq[v]) { inq[v] = true; Q.push(v); }
}
}
}
}
//裸的spfa不解释 int dp[N]; //记忆化搜索所记忆的东西（表示到这个点最短路的条数）
int dfs(int u, int deep) { //deep存储从1到这个点的深度
if (dp[u]) return dp[u]; //如果已经到过这个点直接返回条数
Travel(i, u, G) {
int v = G.to[i];
if (deep - == dis[v]) //如果deep-1等于之前算出来的dis（最短路径）
//也就是说，当前我们所走的路径是可以走通的最短路之一
dp[u] = (dp[u] + dfs(v, deep-)) % mod; //计算路径个数，并继续向下递归
//很简单的一个加法原理
}
return dp[u]; //最后记得返回这个值
} int main (){
G.init();
int n = read(), m = read();
while (m--) {
int u = read(), v = read();
G.add_edge(u, v, );
G.add_edge(v, u, );
}
spfa();
dp[] = ;
For (i, , n)
dp[i] = dfs(i, dis[i]);
//我们从每一个点向起点走回去，所以一开始的深度是当前这个点的最短路
//这样可以解释之前为什么是deep-1了
For (i, , n)
printf ("%d\n", dp[i]);
//最后输出结果
}