洛谷P1608《路径统计》

一月 20, 2020 2405

《最短路计数》加上一点小细节

解析

具体实现思想就不说了。说一点要注意的细节：

判重！！！

本题有重边，而且重边似乎不算不同路径？

所以要对本题的加边稍加修改

1
2
3
4
5
6
7
8
9
10
11
int minEdge[MAXN][MAXN];

// ...

for (int i = 1; i <= e; ++i) {
    int u, v, w; scanf("%d %d %d", &u, &v, &w); 
    if (minEdge[u][v] == 0 || minEdge[u][v] >= w) {
        minEdge[u][v] = w;
        head[u].push_back(Edge(v, w));
    }
}

剩下就没了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//
//  LuoguP1608.cpp
//  Debugging
//
//  Created by HandwerSTD on 2019/9/7.（9月7号的代码次年1月才写完。。。）
//  Copyright © 2019 HandwerSTD. All rights reserved.
//
//

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

const int MAXN = 2000 + 10;

struct Edge { int v, w; Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {} };
struct Node {
    int now, wt;
    Node(int _n = 0, int _w = 0) : now(_n), wt(_w) {}
    bool operator < (const Node &that) const {
        return wt > that.wt;
    }
};

int n, e;
std::vector<Edge> head[MAXN];
int dis[MAXN], ans[MAXN];
int minEdge[MAXN][MAXN];
bool vis[MAXN];
std::priority_queue<Node> q;

void SPFA() {
    memset(dis, 0x3f, sizeof dis);
    q.push(Node(1, 0)); dis[1] = 0; ans[1] = 1;
    while (!q.empty()) {
        Node nwn = q.top(); q.pop();
        int u = nwn.now;
        if (vis[u]) continue; vis[u] = true;
        for (int i = 0, siz = (int) head[u].size(); i < siz; ++i) {
            int v = head[u][i].v, w = head[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                ans[v] = ans[u];
                q.push(Node(v, dis[v]));
            } else if (dis[v] == dis[u] + w) {
                ans[v] += ans[u];
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &e);
    for (int i = 1; i <= e; ++i) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w); 
        if (minEdge[u][v] == 0 || minEdge[u][v] >= w) {
            minEdge[u][v] = w;
            head[u].push_back(Edge(v, w));
        }
    }
    SPFA();
    if (dis[n] == 0x3f3f3f3f) printf("No answer\n");
    else printf("%d %d\n", dis[n], ans[n]);
    return 0;
}