HDU 1142 A Walk Through the Forest （求最短路条数）

A Walk Through the Forest

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1142

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

Hint

##题意：求最短路的条数. 要求这些路径互相没有相同的边.
##题解：直接标记出最短路中的边，对这些边dfs一次即可. 注意：应该求终点到其他点的最短路，再从起点开始dfs. (或反过来)
若要求各条最短路不共边，则需要用最大流. [HDU3416-Marriage Match IV](http://acm.hust.edu.cn/vjudge/contest/122685#problem/Q) 题解：http://www.cnblogs.com/Sunshine-tcf/p/5752180.html
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 501000 #define mod 1000000007 #define inf 0x3f3f3f3f #define IN freopen("in.txt","r",stdin); using namespace std;

int n, m;
typedef pair<int,int> pii;
priority_queue<pii,vector,greater > q;
bool vis[maxn];
int edges, u[maxn], v[maxn], w[maxn];
int first[maxn], _next[maxn];
int dis[maxn];
int pre[maxn];

void add_edge(int s, int t, int val) {
u[edges] = s; v[edges] = t; w[edges] = val;
_next[edges] = first[s];
first[s] = edges++;
}

void dijkstra(int s) {
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
for(int i=1; i<=n; i++) dis[i]=inf; dis[s] = 0;
while(!q.empty()) q.pop();
q.push(make_pair(dis[s], s));

while(!q.empty()) {
    pii cur = q.top(); q.pop();
    int p = cur.second;
    if(vis[p]) continue; vis[p] = 1;
    for(int e=first[p]; e!=-1; e=_next[e]) if(dis[v[e]] > dis[p]+w[e]){
        dis[v[e]] = dis[p] + w[e];
        q.push(make_pair(dis[v[e]], v[e]));
        pre[v[e]] = p;
    }
}

}

int cnt[maxn];
//必须记忆化dfs：直接dfs-TLE bfs-MLE
int dfs(int s) {
if(s == 2) return 1;
if(cnt[s] != -1) return cnt[s];
int sum = 0;
for(int e=first[s]; e!=-1; e=_next[e]) //if(dis[v[e]]+w[e] == dis[u[e]]) {
if(dis[v[e]] < dis[u[e]]) {
sum += dfs(v[e]);
}
return cnt[s] = sum;
}

int main(void)
{
//IN;

while(scanf("%d", &n) != EOF && n)
{
    memset(first, -1, sizeof(first)); edges = 0;
    memset(cnt, -1, sizeof(cnt));
    cin >> m;

    while(m--) {
        int u,v,w; scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    dijkstra(2);

    int ans = dfs(1);

    printf("%d
", ans);
}

return 0;

}