题目：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1858

uva访问不到的可以去vjudge上：https://vjudge.net/problem/UVA-10917

题目大意是说有两个点1，2. 从1出发走到2，每次只走可以make progress的路径， 所谓的make progress的A到B的边指的是从存在B到2的某条路比A到2的任何路的长度都要小，实际上就是B到2的最短路比A到2的最短路要短。可以用单源最短路求出2出发的所有最短路，然后从1开始做一个DFS就可以求出正确答案。但是需要注意的就是这个DFS要记忆化一下，否则会TLE

AC代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int MAXN = 1005;
const int MAXM = 1000005;
const int INF = (int) 1e9;
int cntedge;

struct EDGE {
    int from, to, weight, next_edge = -1;

    EDGE() {}

    EDGE(int f, int t, int w, int n) : from(f), to(t), weight(w), next_edge(n) {}
} edge[MAXM << 1];

int head[MAXN];
bool vis[MAXN];
long long dist[MAXN];

inline void init(int n, int m) {
    fill(vis, vis + n, false);
    fill(dist, dist + n, INF);
    fill(head, head + n, -1);
    for (int i = 0; i < m; ++i) { edge[i].next_edge = -1; }
    cntedge = 0;
}

inline void addedge(int from, int to, int weight) {
    edge[cntedge] = EDGE(from, to, weight, head[from]);
    head[from] = cntedge++;
}

struct nd {
    long long d;
    int v;

    nd(long long _d, int _v) : d(_d), v(_v) {}

    friend bool operator>(const nd &a, const nd &b) { return a.d > b.d; }
};

void dijkstra(int s) {
    dist[s] = 0;
    priority_queue<nd, vector<nd>, greater<nd>> q;
    q.push(nd(0, s));
    while (!q.empty()) {
        nd p = q.top();
        q.pop();
        if (vis[p.v])continue;
        long long u = p.v;
        vis[u] = true;
        for (int e = head[u]; e != -1; e = edge[e].next_edge) {
            int v = edge[e].to;
            int w = edge[e].weight;
            if (p.d + w < dist[v] && !vis[v]) {
                dist[v] = p.d + w;
                q.push(nd(dist[v], v));
            }
        }
    }
}

int dp[MAXN];

int validPathCnt(int st, int ed) {
    if (st == ed) { return 1; }
    if (dp[st] != -1)return dp[st];
    int ret = 0;
    for (int e = head[st]; e != -1; e = edge[e].next_edge) {
        if (dist[edge[e].to] <= dist[st])continue;
        ret += validPathCnt(edge[e].to, ed);
    }
    return dp[st] = ret;
}

int main() {
    while (true) {
        static int n, m;
        scanf("%d", &n);
        if (!n)break;
        scanf("%d", &m);
        init(n + 2, m * 2 + 2);
        for (int i = 0; i < m; ++i) {
            static int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dijkstra(2);
        fill(dp, dp + n + 1, -1);
        printf("%d\n", validPathCnt(2, 1));
    }
    return 0;
}