学步园

大意：Jimmy下班后需要穿过一个森林。他只沿着满足如下条件的道路(A,B)走：存在一条从B出发回家的路径，比所有从A出发回家的路径都短。你的任务是计算有多少条不同的路径。

思路：以终点做一遍最短路径，当d[B]<d[A]，则连一条有向边A->B，题目的目标就是求出起点到终点的路径条数，由于是DAG图，可以用动态规划的方法去写。

f[i]表示从i出发走到终点的不同路径的条数，边界条件是f[end] = 1，可以用记忆化搜索去实现，一般搜索会超时。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

const int maxn = 1010;
const int INF = 0x3f3f3f3f;
const int src = 1;
const int end = 2;

int g[maxn][maxn];
int G[maxn][maxn];

int n, m;

int d[maxn];
int f[maxn];
bool vis[maxn];

void init()
{
	memset(vis, 0, sizeof(vis));
	memset(g, INF, sizeof(g));
	memset(f, 0, sizeof(f));
}

int read_case()
{
	init();
	scanf("%d", &n);
	if(!n) return 0;
	scanf("%d", &m);
	while(m--)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = g[v][u] = w;
	}
	return 1;
}

void Dijkstra(int src)
{
	bool vis[maxn] = {0};
	for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF;
	for(int i = 1; i <= n; i++)
	{
		int x, m = INF;
		for(int y = 1; y <= n; y++) if(!vis[y] && d[y] <= m) m = d[x=y];
		vis[x] = 1;
		for(int y = 1; y <= n; y++) d[y] = min(d[y], d[x] + g[x][y]);
	}
}

int dp(int i, int end)
{
	int &ans = f[i];
	if(vis[i]) return ans;
	vis[i] = 1;
	ans = 0;
	if(i == end) ans = 1;
	else for(int j = 1; j <= n; j++) if(g[i][j] != INF && d[i] > d[j])
	{
		ans += dp(j, end);
	}
	return ans;
}

void solve()
{
	Dijkstra(end);
	int ans = dp(1, 2);
	printf("%d\n", ans);
}

int main()
{
	while(read_case())
	{
		solve();
	}
	return 0;
}