题目链接：http://codeforces.com/contest/208/problem/C
思路：题目要求的是经过1~N的最短路上的某个点的路径数 / 最短路的条数的最大值。一开始我是用spfa得到从1开始的最短路和从N开始的最短路，然后分别从N开始记忆化搜索，得到从1到达最短路径上的u的路径条数，记作dp1[u], 然后再从1开始搜，得到最短路径上从N到达某个点u的路径条数，记作dp2[u],于是经过某个点u的最短路径数目为dp1[u] * dp2[u]，然后只需枚举u求最大值即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; const int MAX_N = (100 + 10);
int N, M;
long long dp1[MAX_N], dp2[MAX_N];
int vis[MAX_N], dist1[MAX_N], dist2[MAX_N];
vector<int > g[MAX_N]; void spfa(int st, int ed, int *dist)
{
memset(vis, 0, sizeof(vis));
queue<int > que;
que.push(st);
dist[st] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
vis[u] = 0;
REP(i, 0, (int)g[u].size()) {
int v = g[u][i];
if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
if (!vis[v]) { vis[v] = 1; que.push(v); }
}
}
}
} long long dfs1(int u, int fa)
{
if (u == 1) return dp1[u] = 1;
if (~dp1[u]) return dp1[u];
long long ans = 0;
REP(i, 0, (int)g[u].size()) {
int v = g[u][i];
if (v != fa && dist1[v] + 1 == dist1[u]) {
ans += dfs1(v, u);
}
}
return dp1[u] = ans;
} long long dfs2(int u, int fa)
{
if (u == N) return dp2[u] = 1;
if (~dp2[u]) return dp2[u];
long long ans = 0;
REP(i, 0, (int)g[u].size()) {
int v = g[u][i];
if (v != fa && dist2[v] + 1 == dist2[u]) {
ans += dfs2(v, u);
}
}
return dp2[u] = ans;
} int main()
{
while (cin >> N >> M) {
FOR(i, 1, N) g[i].clear();
FOR(i, 1, M) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(dist1, 0x3f, sizeof(dist1));
memset(dist2, 0x3f, sizeof(dist2));
spfa(1, N, dist1);
spfa(N, 1, dist2);
memset(dp1, -1, sizeof(dp1));
memset(dp2, -1, sizeof(dp2));
long long a = dfs1(N, -1);
double ans = 1.0;
dfs2(1, -1);
FOR(i, 1, N) if (dp1[i] >= 1 && dp2[i] >= 1) {
if (i == 1 || i == N) ans = max(ans, 1.0 * dp1[i] * dp2[i] / a);
else ans = max(ans, 2.0 * dp1[i] * dp2[i] / a);
}
printf("%.9f\n", ans);
}
return 0;
}
后来看了别人的做法，发现有更加简单的做法，直接用floyd做就可以了。dist[u][v]表示u到v的最短路径长度，dp[u][v]表示此最短路径长度对应的最短路径数目，然后就是更新的时候注意一下就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; const int MAX_N = (100 + 100);
int N, M;
long long dist[MAX_N][MAX_N], dp[MAX_N][MAX_N]; int main()
{
while (cin >> N >> M) {
memset(dist, 0x3f, sizeof(dist));
memset(dp, 0, sizeof(dp));
FOR(i, 1, M) {
int u, v; cin >> u >> v;
dist[u][v] = dist[v][u] = 1;
dp[u][v] = dp[v][u] = 1;
}
FOR(k, 1, N) {
FOR(i, 1, N) {
FOR(j, 1, N) if (dist[i][k] + dist[k][j] <= dist[i][j]) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
dp[i][j] = dp[i][k] * dp[k][j];
}
else {
dp[i][j] += dp[i][k] * dp[k][j];
}
}
}
}
double ans = 1.0;
FOR(i, 2, N - 1) {
if (dist[1][i] + dist[i][N] == dist[1][N]) ans = max(ans, 2.0 * dp[1][i] * dp[i][N]/ dp[1][N]);
}
printf("%.7f\n", ans);
}
return 0;
}