题目链接：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;

}