题目链接
题目大意：你扮演救生队长，在某个城市发生灾难时中召集救生队对该城市进行援救。
给定各个城市之间的通路以及通路的路程，灾难发生时你所在的城市，灾难发生时的城市，各个城市的救生队数目。求出你从你所在的城市出发，到救灾城市的最短路的数量，以及这些最短路中所能召集到最多的救灾队数目。
其实就是求图最短路径的数量以及最短路径中，结点累加权值最大的最短路径。
博主在写的时候，初期使用的是未优化的 Dijkstra 算法，但是 PAT 指出段错误，博主误以为代码时间复杂度较高，于是学习了一下优先队列和前向星，对 Dijkstra 算法进行了堆优化，有心的同学可以试试，在 这里（洛谷 -- P3371 【模板】单源最短路径（弱化版）） 可以测试堆优化后的 Dijkstra 算法。下面是该算法的代码
#include<iostream>
#include<vector> // 创建优先队列所需
#include<queue> // 创建优先队列所需
#include<cstdio> // 初始化数组所需
#include<cstring> // memset 所需
using namespace std;
// 数据边界
const int maxn = 10010, maxm = 500010, max_int = 2147483647;
// 记录源点到各结点之间的距离
int dist[maxn];
// 记录该结点是否被访问过
bool tags[maxn];
// 构建前向星 分别为：记录存储当前边的位置、记录边的权值、记录有向边所连接的下一个节点、记录当前边的前一条边所存储的位置、记录当前是第几条边
int head[maxm], w[maxm], to[maxm], nxt[maxm], cnt = 0;
// 城市数目、城市之间通路数、所在城市、目标城市
int n, m, s, a;
// 构建优先队列用到的方法
struct cmp {
bool operator()(int x, int y)
{
return dist[x] > dist[y]; // dist[x] > dist[y] 为小顶堆，dist[x] < dist[y] 为大顶堆
}
};
// 构建前向星
void front_edge(int nx, int mx, int wx) {
to[cnt] = mx;
w[cnt] = wx;
nxt[cnt] = head[nx];
head[nx] = cnt++;
return;
}
// Dijikstra 算法
void dijkstra(int s) {
// 创建优先队列
priority_queue<int, vector<int>, cmp> q;
while (!q.empty())
q.pop();
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.top();
q.pop();
if (!tags[x]) {
tags[x] = true;
for (int i = head[x]; i != -1; i = nxt[i]) {
int y = to[i];
dist[y] = min(dist[y], dist[x] + w[i]);
q.push(y);
}
}
}
return;
}
int main() {
cin >> n >> m >> s;
memset(head, -1, sizeof(head));
memset(tags, false, sizeof(tags));
for (int i = 1; i <= n; i++)
dist[i] = max_int;
for (int i = 1; i <= m; i++) {
int nx, mx, wx;
cin >> nx >> mx >> wx;
front_edge(nx, mx, wx);
}
dijkstra(s);
for (int i = 1; i <= n; i++)
cout << dist[i] << " ";
}
return 0;
}
坑点1
由于题目中需要求解最短边的数量，因此要对 Dijkstra 算法进行改写
通过对前向星以及优先队列的学习之后，我们可以发现，在每次使用前向星寻边的时候，可以使用一个数组，记录下来源点到该结点的最短距离，这个最短距离通过判断 dist[y] 是否变更进行改变。也就是修改 Dijkstra 函数中的代码如下
// 根据题目创建的全局变量
const int maxn = 600;
// 记录能够召集到的最多队伍数目
int nodeMaxTeam[maxn];
// min_edges[maxn] 需要在 main() 函数中初始化为全1，因为假定源点到各个结点的路径起始只有一条
int min_edges[maxn];
// 记录个城市所拥有的队伍数
int Teams[maxn];
void dijkstra(int s) {
// 创建优先队列
priority_queue<int, vector<int>, cmp> q;
while (!q.empty())
q.pop();
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.top();
q.pop();
if (!tags[x]) {
tags[x] = true;
for (int i = head[x]; i != -1; i = nxt[i]) {
int y = to[i];
// 被的修改代码
temp = dist[y];
dist[y] = min(dist[y], dist[x] + w[i]);
if(dist[y] != temp)
min_edges[y]++;
else
min_edges[y] = 1;
nodeMaxTeam[y] = max(nodeMaxTeam[y], nodeMaxTeam[x] + Teams[y]);
q.push(y);
}
}
}
return;
}
但是这里有一个反例
4 5 0 3
1 4 1 2
0 1 1
0 2 2
0 3 4
1 2 1
2 3 2
正确输出为
3 8
这里错误的原因是：我并没有考虑若从结点 1 到 结点 3 之间经过的 结点 2 和 结点 1 之间的通路有多条时，上述算法只能够找到两条。因此改进上述算法如下：
坑点2
// 根据题目创建的全局变量
const int maxn = 600;
// 记录能够召集到的最多队伍数目
int nodeMaxTeam[maxn];
// min_edges[maxn] 需要在 main() 函数中初始化为全1，因为假定源点到各个结点的路径起始只有一条
int min_edges[maxn];
// 记录个城市所拥有的队伍数
int Teams[maxn];
void dijkstra(int s) {
priority_queue<int, vector<int>, cmp> q;
while (!q.empty())
q.pop();
dist[s] = 0;
nodeMaxTeam[s] = Teams[s];
q.push(s);
while (!q.empty()) {
int x = q.top();
q.pop();
if (!tags[x]) {
tags[x] = true;
for (int i = head[x]; i != -1; i = nxt[i]) {
int y = to[i];
// 修改的代码块
// 第一种情况 找到较短的边
if (dist[y] > dist[x] + w[i]) {
/*
由于该点到原点的最短边条数取决于上一个点（DP思想），因此若最短边发生变化，
该条数也应该随之更新为，所找到的最短距离对应的顶点 到源点的最短边数
*/
min_edges[y] = min_edges[x];
// 源点到目标点的路径变更，因此修改最大队伍数
nodeMaxTeam[y] = nodeMaxTeam[x] + Teams[y];
// 修改最短路径
dist[y] = dist[x] + w[i];
// 将 y 点入队列，以便对 y 所连接的所有边进行再次决策
q.push(y);
}
else if (dist[y] == dist[x] + w[i]) { // 第二种情况 找到相等的边
// 当前的结点(y)的最短边数，加上源点到链接到当前结点的结点(x)，其到源点的最短边数
min_edges[y] += min_edges[x];
// 若该路径召集的队伍比之前多，则更新召集到的最多队伍数目
if(nodeMaxTeam[y] < nodeMaxTeam[x] + Teams[y])
nodeMaxTeam[y] = nodeMaxTeam[x] + Teams[y];
}
// 修改的代码块
}
}
}
return;
}
然后，当我很开心的提交到 OJ 时，发现仍然有两条测试没过。经过思考之后想到，该题所采用的是无向图，因此通路是双向的，我所使用的 Dijkstra 算法是单向的，因此需要修改前向星，使得通路变成双向的，修改 main() 函数如下：
int main() {
cin >> n >> m >> s >> a;
memset(head, -1, sizeof(head));
memset(tags, false, sizeof(tags));
for (int i = 0; i < n; i++) {
dist[i] = max_int;
nodeMaxTeam[i] = 0;
min_edges[i] = 1;
}
for (int i = 0; i < n; i++)
cin >> Teams[i];
for (int i = 0; i < m; i++) {
int nx, mx, wx;
cin >> nx >> mx >> wx;
front_edge(nx, mx, wx);
// 增加的处理
front_edge(mx, nx, wx);
// 增加的处理
}
dijkstra(s);
cout << min_edges[a] << " " << nodeMaxTeam[a];
return 0;
}
完整代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 600, maxm = 500010, max_int = 2147483647;
int dist[maxn];
bool tags[maxn];
int head[maxm], w[maxm], to[maxm], nxt[maxm], cnt = 0;
int n, m, s, a;
int min_edges[maxn];
int Teams[maxn], nodeMaxTeam[maxn];
struct cmp {
bool operator()(int x, int y)
{
return dist[x] > dist[y];
}
};
void front_edge(int nx, int mx, int wx) {
to[cnt] = mx;
w[cnt] = wx;
nxt[cnt] = head[nx];
head[nx] = cnt++;
return;
}
void dijkstra(int s) {
priority_queue<int, vector<int>, cmp> q;
while (!q.empty())
q.pop();
dist[s] = 0;
nodeMaxTeam[s] = Teams[s];
q.push(s);
while (!q.empty()) {
int x = q.top();
q.pop();
if (!tags[x]) {
tags[x] = true;
for (int i = head[x]; i != -1; i = nxt[i]) {
int y = to[i];
if (dist[y] > dist[x] + w[i]) {
min_edges[y] = min_edges[x];
nodeMaxTeam[y] = nodeMaxTeam[x] + Teams[y];
dist[y] = dist[x] + w[i];
q.push(y);
}
else if (dist[y] == dist[x] + w[i]) {
min_edges[y] += min_edges[x];
if(nodeMaxTeam[y] < nodeMaxTeam[x] + Teams[y])
nodeMaxTeam[y] = nodeMaxTeam[x] + Teams[y];
}
}
}
}
return;
}
int main() {
cin >> n >> m >> s >> a;
memset(head, -1, sizeof(head));
memset(tags, false, sizeof(tags));
memset(nodeMaxTeam, 0, sizeof(nodeMaxTeam));
for (int i = 0; i < n; i++) {
dist[i] = max_int;
// 我试图用 memset 初始化 min_edges 数组时答案错误，以后填坑，可能是 memset 的问题
min_edges[i] = 1;
}
for (int i = 0; i < n; i++)
cin >> Teams[i];
for (int i = 0; i < m; i++) {
int nx, mx, wx;
cin >> nx >> mx >> wx;
front_edge(nx, mx, wx);
front_edge(mx, nx, wx);
}
dijkstra(s);
cout << min_edges[a] << " " << nodeMaxTeam[a];
return 0;
}
总结：
- 本体可以用 O (N2) 的未优化算法通过，较容易理解实现，因此同学们可以尝试一下
- 博主由于将 求最短路径数 错看成了 求最短路径长度 浪费了3天的时间 QAQ
- 上述的两个坑点希望大家一定注意