UVA10917 Walk Through the Forest（最短路+记忆化搜索dp）

A Walk Through the Forest

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10214
Accepted Submission(s): 3721

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

Sample Output

2
4

Source

University of Waterloo Local Contest 2005.09.24

链接

https://cn.vjudge.net/problem/UVA-10917

题意

Jimmy打算每天沿着一条不同的路径回家，欣赏不同的风景，但是他不打算走“回头路”，所以他只沿着满足如下条件的道路(A,B)走：存在一条从B出发回家的路径，比所有从A出发回家的路径都短。计算有多少条不同的回家路径。

题解

首先求出从每个点u回家的最短路径长度d[u]，则题目中的条件“存在一条从B出发回家的路径，比所有从A出发回家的路径都短”实际上是指d[B]<d[A]。这样，我们创建一个新的图，当且仅当d[B]<d[A]时加入有向边$A\rightarrow B$，则题目的要求是求出起点到终点的路径条数。因为这个图是DAG，可以使用动态规划求解。
小白书——P330

DAG求解任意两点间的路径数以及最长路径，使用dp记忆化搜索完成。

代码

Status	Accepted
Time	10ms
Length	2214

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 10010;
int dist[maxn], dp[maxn];
bool vis[maxn];
int n, m, s, t;

struct Node
{
    int v, c;
    Node (int _v, int _c): v(_v), c(_c){}
    bool operator < (const Node &r) const
    {
        return c > r.c;
    }
};

struct Edge
{
    int to, c;
    Edge(){}
    Edge(int _to, int _c): to(_to), c(_c){}
};
vector <Edge> edge[maxn];

void addedge(int u, int v, int w)
{
    edge[u].push_back(Edge(v, w));
}

void dijkstra(int s) // 最短路
{
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= n; ++i)
        dist[i] = inf;
    dist[s] = 0;
    priority_queue <Node> Q;
    Q.push(Node(s, 0));
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < edge[u].size(); ++i)
        {
            int v = edge[u][i].to;
            if (!vis[v] && dist[v] > dist[u] + edge[u][i].c)
            {
                dist[v] = dist[u] + edge[u][i].c;
                Q.push(Node(v, dist[v]));
            }
        }
    }
}

int dfs(int u) // 求解u到t的路径数量，记忆化搜索dp
{
    int &ans = dp[u];
    if (ans != -1) // 已经搜索过，直接返回
        return ans;
    if (u == s) // 到达终点
        return 1;
    ans = 0;
    for (int i = 0; i < edge[u].size(); ++i)
    {
        int v = edge[u][i].to;
        if (dist[v] > dist[u]) // dfs条件，往距离大的方向走
            ans += dfs(v);
    }
    return ans;
}

int main()
{
//    freopen("/Users/taifu/Codes/NOW/data.in", "r", stdin);
//    freopen("/Users/taifu/Codes/NOW/data.out","w",stdout);
    int u, v, w;
    while (scanf("%d", &n) != EOF && n)
    {
        if (n == 0)
            break;
        scanf("%d", &m);
        for (int i = 1; i <= n; ++i) // 未清空1WA
            edge[i].clear();
        s = 1, t = 2; // 起点终点
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dijkstra(t);
        memset(dp, -1, sizeof(dp));
        int ans = dfs(t); // dp寻找路径
        printf("%d\n", ans);
    }
    return 0;
}

没有清空边集vector向量，WA了一发。

The end.
2018-08-21 星期二