洛谷P1608《路径统计》

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

解析

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

判重!!!

本题有重边,而且重边似乎不算不同路径?

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

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
//
// 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;
}