UVa 10917. Walk Through the Forest

2018-09-09

Description

Jimmy的辦公室在森林的一邊，而他的家在森林的另一邊。
Jimmy想要每天都走不同的路徑回家。但是他也不想要回家太晚，所以他總是選擇一條可以朝他家「前進」的路徑來走。所謂「前進」指的是他會選擇從A點走到B點如果B點存在一條到他家的路徑長度比A點到他家任一路徑的長度都來的短的話。請你算出Jimmy共有多少種不同的路徑可以走。

Input Format

輸入包含多筆測資
第一列包含兩個整數N$(1 < N \le 1000)$和M，N代表有多少點(編號從1到N，請注意：編號1的點為Jimmy的辦公室，編號2的點為Jimmy的家)，M代表共有多少個連接2個點的邊。接下來的M列每列有3個整數 a, b, d。a,b為點的編號，d 為連接 a,b 的路徑長（在這裡 a,b 不會相同，$1 \le d \le 1000000$）。路徑是雙向的，且任2點之間僅有一條路徑連接。

Output Format

每組測試資料輸出一列，Jimmy共有多少種不同的路徑可以走。

Sample Input

Sample Output

2
4

UVa - 10917
翻譯來源：Luckycat

Solution

這題還滿有趣的，因為朝家「前進」，所以需要重新構圖。
由於每步都會朝他家「前進」，所以可以先想到對於點2去做單源最短路徑(Dijkstra)。
然後再重新構圖，且這邊要注意是有向邊。
注意：以下Code點的編號是從0到N-1

Code

/*************************************************************************
  > File Name: 10917 - A Walk Through the Forest.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Tue Sep  4 12:04:50 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> link[1001];
vector<int> rebuild[1001];
const int inf = 1 << 30;
int distant[1001];
int dp[1001];
bool visit[1001];
int n, m;

struct node {
    int dis, index;
    bool operator< (const node &b) const {
        return dis > b.dis;
    }
    node() {}
    node(int d, int i) : dis(d), index(i) {}
};
int dfs(int now) {
    if (now == 1)
        return 1;
    if (dp[now] == -1) {
        dp[now] = 0;
        for (auto i : rebuild[now])
            dp[now] += dfs(i);
    }
    return dp[now];
}
void dijkstra() {
    priority_queue<node> pq;
    pq.push(node(0, 1));
    int cur;
    distant[1] = 0;
    while (!pq.empty()) {
        cur = pq.top().index;
        pq.pop();
        if (visit[cur])
            continue;
        visit[cur] = 1;
        for (auto i : link[cur]) {
            int next = i.first;
            int dis = i.second;
            if (distant[next] > distant[cur] + dis) {
                distant[next] = distant[cur] + dis;
                pq.push(node(distant[next], next));
            }
        }
    }
}
void build() {
    memset(dp, -1, sizeof(dp));
    int next, dis;
    for (int i = 0; i < n; i++) {
        rebuild[i].clear();
        for (auto j : link[i])
            if (distant[i] > distant[j.first])
                rebuild[i].emplace_back(j.first);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a, b, c;
    while (cin >> n >> m && n) {
        memset(link, 0, sizeof(link));
        memset(visit, 0, sizeof(visit));
        for (int i = 0;i < n; i++)
            distant[i] = inf;
        while (m--) {
            cin >> a >> b >> c;
            link[--a].push_back({--b, c});
            link[b].push_back({a, c});
        }
        dijkstra();
        build();
        cout << dfs(0) << '\n';
    }
}