hdu1142(最短路+记忆化搜索)

 1 #include <bits/stdc++.h>
 2 
 3 struct Edge
 4 {
 5     int v, w;
 6     Edge(int _v, int _w): v(_v), w(_w){}
 7 };
 8 
 9 const int MAXN = 1000 + 10;
10 
11 std::vector<Edge> E[MAXN];
12 
13 int n, m, dp[MAXN];
14 
15 bool vis[MAXN];
16 int dist[MAXN];
17 
18 void init()
19 {
20     memset(vis, false, sizeof(vis));
21     memset(dp, 0, sizeof(dp));
22     for(int i = 1; i <= n; ++ i){
23         dist[i] = 1<<30;
24         E[i].clear();
25     }
26 }
27 
28 void addEdge(int a, int b, int d)
29 {
30     E[a].push_back(Edge(b, d));
31     E[b].push_back(Edge(a, d));
32 }
33 
34 void spfa(int start)
35 {
36     vis[start] = true;
37     dist[start] = 0;
38     std::queue<int> que;
39     que.push(start);
40     while(que.empty()==false){
41         int u = que.front();
42         que.pop();
43         vis[u] = false;
44         for(int i = 0; i < E[u].size(); ++ i){
45             int v = E[u][i].v;
46             int w = E[u][i].w;
47             if(dist[v] > dist[u] + w){
48                 dist[v] = dist[u] + w;
49                 if(vis[v] == false){
50                     que.push(v);
51                 }
52             }
53         }
54     }
55 }
56 
57 
58 int dfs(int u)
59 {
60     if(u == 2)
61         return 1;
62     if(dp[u] > 0){
63         return dp[u];
64     }
65     for(int i = 0; i < E[u].size(); ++ i){
66         int v = E[u][i].v;
67         if(dist[u] > dist[v]){
68             dp[u] += dfs(v);
69         }
70     }
71     return dp[u];
72 }
73 
74 int main()
75 {
76     while(scanf("%d", &n) && n){
77         scanf("%d", &m);
78         init();
79         for(int i = 1; i <= m; ++ i){
80             int a, b, d;
81             scanf("%d%d%d", &a, &b, &d);
82             addEdge(a, b, d);
83         }
84         spfa(2);
85         printf("%d
", dfs(1));
86     }
87 }