題目：
A Walk Through the Forest
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3689 Accepted Submission(s): 1340
Problem Description
Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable.
The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take.
Input
Input contains several test cases followed by a line containing 0. Jimmy has numbered each intersection or joining of paths starting with 1. His office is numbered 1, and his house is numbered 2. The first line of each test case gives the number of intersections N, 1 < N ≤ 1000, and the number of paths M. The following M lines each contain a pair of intersections a b and an integer distance 1 ≤ d ≤ 1000000 indicating a path of length d between intersection a and a different intersection b. Jimmy may walk a path any direction he chooses. There is at most one path between any pair of intersections.
Output
For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed 2147483647
Sample Input
5 6
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 24
7 8
1 3 1
1 4 1
3 7 1
7 4 1
7 5 1
6 7 1
5 2 1
6 2 1
0
Sample Output
2
4
分析與總結：
做這題真可謂是一波三折， 足足WA了有30+次。
1. 題目意思理解錯誤。題目中的一段話沒理解好：
He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A.
這句話的意思是說，對於兩點A，B， 如果點B到達家裡的最短路距離小於點A到達家裡的最短路距離，那麼點A就可以到達點B。
而我把這題理解成了求有辦公室到家裡有多少條不同的最短路。
2. 解決了上述錯誤之後，接下來可以求出每一點到達點2（家裡）的最短路，然後根據所求的各點最短路，求出有多少條到家裡的路徑。
如果直接搜索是會超時的，所以要用記憶化搜索。
3. 因為自己的粗心， 由於我的程序中有兩個數組名為d和dp， 在寫記憶話搜索時把這兩個數組混淆了，結果又WA了十多次而找不到原因。
代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
#include<string>
#include<map>
using namespace std;
typedef int Type;
typedef pair<Type,int>pii;
const Type INF = 0x7fffffff;
const int VN = 1005;
const int EN = VN*VN;
int n,m,size;
int head[VN];
Type d[VN];
bool G[VN][VN];
bool vis[VN];
int cnt;
int dp[VN];
struct Edge{
int v,next;
Type w;
}E[EN];
void init(){
size=0;
cnt=0;
memset(G, 0, sizeof(G));
memset(head, -1, sizeof(head));
memset(dp, -1, sizeof(dp));
}
void addEdge(int u,int v,Type w){
E[size].v=v;
E[size].w=w;
E[size].next=head[u];
head[u]=size++;
}
void Dijkstra(int src){
for(int i=1; i<=n; ++i) d[i]=INF;
d[src] = 0;
priority_queue<pii,vector<pii>,greater<pii> >q;
q.push(make_pair(d[src],src));
while(!q.empty()){
pii x = q.top(); q.pop();
int u = x.second;
if(d[u] != x.first)continue;
for(int e=head[u]; e!=-1; e=E[e].next){
Type tmp=d[u]+E[e].w;
if(d[E[e].v] > tmp){
d[E[e].v] = tmp;
q.push(make_pair(tmp, E[e].v));
}
}
}
}
int dfs(int u){
if(dp[u]!=-1) return dp[u];
if(u==2) return 1;
int cnt=0;
for(int v=1; v<=n; ++v)if(d[v]<d[u] && G[u][v]){
cnt += dfs(v);
}
dp[u] = cnt;
return dp[u];
}
int main(){
int u,v;
Type w;
while(~scanf("%d",&n)&n){
scanf("%d",&m);
init();
for(int i=0; i<m; ++i){
scanf("%d%d%d",&u,&v,&w);
G[u][v] = G[v][u] = 1;
addEdge(u,v,w);
addEdge(v,u,w);
}
Dijkstra(2);
printf("%d\n", dfs(1));
}
return 0;
}
