题目
假设你是一个城市的紧急救援队队长，你会得到一张你国家的特别地图。当有紧急电话从其他城市打给你时，你的工作是尽快带你的人到那个地方，同时，在路上尽可能多地召集人手。
输入的数：
| 行数 | 数字 | 含义 | ||
|---|---|---|---|---|
| 第一行 | N 城市数量 <=500 | N道路数量 | C1 你当前所在城市 | C2 你需要保护的城市 |
| 第二行 | N个数 | 第i个数字表示第i个城市还有几个rescue team | ||
| 第三行 | 3个数 | 城市1 | 城市2 | 城市1到城市2的距离 |
| 第四行 | 同上 | |||
| 第...行 | 同上 |
输出的数：
| 第一个数 | 第二个数 |
|---|---|
| C1到C2的最短距离 | 最大能救出的rescue team 数量 |
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4
解法
法一：C++
思路：
这是graph求最短路径的问题。解决该问题的算法有（我学过的）：1.DFS深度优先搜索算法；2.Dijkstra算法；3.BFS；4.A*.
这里选择Dijkstra算法。
先上源码，再结合源码来分析。
源码：
！！这段代码摘自网上，网址不小心丢失了！！特此声明
这位作者的注释写的也很全，炒鸡棒
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, c1, c2;//n为顶点数，m为边数，c1为起点，c2为终点
int e[510][510], weight[510], dis[510], num[510], w[510];//题干中说明了N是<=500的，这里设置为510保证不会出现地址越界
bool visit[510];//同上
/*
* e[][]是唯一的二维数组，表示图的邻接矩阵
* weight[]表示每个顶点的点权，就是每个顶点上救援队的数目
* dis[]记录最短距离
* num[]记录最短路径条数
* w[]记录最大点权之和，就是最短路径的路径上的救援队的总数目
* visit[]是一个布尔变量，记录顶点是否被访问，被访问则为true，初值为false表示还没有被访问
*/
const int inf = 99999999;//是一个非常大的数，用于初始化
int main() {
scanf("%d%d%d%d", &n, &m, &c1, &c2);
for(int i = 0; i < n; i++)
{
scanf("%d", &weight[i]);
}
fill(e[0], e[0] + 510 * 510, inf);
fill(dis, dis + 510, inf);
/*
* 两个fill()语句对图的邻接矩阵和最短距离进行初始化。
* 邻接矩阵初始化表示每两个点之间的边权均为无穷大，表示它们之间互不相通；
* 最短距离进行初始化表示目前没有求出任何两点之间的最短距离。
*/
int a, b, c;
for(int i = 0; i < m; i++)//对题目中给出的每对顶点的边权进行赋值
{
scanf("%d%d%d", &a, &b, &c);
e[a][b] = e[b][a] = c;
}
dis[c1] = 0;
//dis[]记录最短路径，初始时还未求出起点的任何出边，因此最短路径设置为0。
w[c1] = weight[c1];
//w[]记录最大点权之和，刚开始是只有起点一个点，因此最大点权之和就是第一个顶点（起点）的点权。
num[c1] = 1;
//只要起点和终点连通，那么至少有一条最短路径，并且题目保证了起点和终点之间一定有一条路径，因此最短路径条数初始为1。
for(int i = 0; i < n; i++)
/*
* 这里为什么要循环n次的原因？
* Dijkstra算法的策略是：设置集合S存放已被访问的顶点，然后执行n次下面的两个步骤（n为顶点个数）
* ①每次从集合V-S中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S；
* ②之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。
* 那么，为什么循环n次就可以了呢？
* 是因为，初始时集合V中有n个顶点，集合S中没有顶点，所以循环n次，将集合V中的顶点全部移至集合S
*/
{
int u = -1, minn = inf;
/*
* 因为顶点的最小值是0，所以初始化为-1表示不表示任何顶点，为之后代替其它顶点做准备；
* minn初始为无穷大，表示初始时任何两点之间不相通。
* u使d[u]最小，MIN存放该最小的d[u]。
*/
for(int j = 0; j < n; j++)
//n为顶点的数目，这里的for循环表示对每个顶点进行遍历
//找到未访问的顶点中d[]最小的
{
if(visit[j] == false && dis[j] < minn)
/*
如果j这个顶点还没有被访问并且起点到j这个顶点的最短路径小于之前求出的当前最短路径，
就用u代替j这个顶点，并且把minn设置为当前最短路径。
*/
{
u = j;
minn = dis[j];
}
}
visit[u] = true;
//标记u为已访问
for(int v = 0; v < n; v++)
//如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优
{
if(visit[v] == false && e[u][v] != inf)
{
if(dis[u] + e[u][v] < dis[v])
//以u为中介点时能令d[v]变小
{
dis[v] = dis[u] + e[u][v];//覆盖dis[v]
num[v] = num[u];//覆盖num[v]
w[v] = w[u] + weight[v];//覆盖w[v]
}
else if(dis[u] + e[u][v] == dis[v])
//找到一条相同长度的路径
{
num[v] = num[v] + num[u];
//注意最短路径条数与点权无关，必须写在if()外面；而且写在if()前还是if()后均可
if(w[u] + weight[v] > w[v])
//以u为中介点时点权之和更大
{
w[v] = w[u] + weight[v];//w[v]继承自w[u]
}
}
}
}
}
printf("%d %d", num[c2], w[c2]);
return 0;
}
Dijkstra代码思路超详细分析
首先
从图上来看，我们将面临的将是这样一张图
figure1 Graph(摘自网上，图侵删)
这张图是有向图，但是题目中其实是无向图的意思，所以只要把箭头去掉想象叫好了。
那么
要画出这样一张图，需要的数据有：
顶点数，边数，权重。
figure 1的权重指的是边的权重，而在题目中的权重是点的权重，也就是各个城市的 rescue team的数量。
同时，需要解决最短路径问题自然需要
起点，终点
所以
题目中第一行输入的数字有了解释
第二行也有了用武之地
int n, m, c1, c2;//n为顶点数，m为边数，c1为起点，c2为终点
int weight[510];//weight[]表示每个顶点的点权，就是每个顶点上救援队的数目
scanf("%d%d%d%d", &n, &m, &c1, &c2);
for(int i = 0; i < n; i++)
{
scanf("%d", &weight[i]);
}
接着
在学习Dijkstra算法时，我们会手绘如下这张图来找出最短路径：
figure 2 Graph的类邻接矩阵(摘自网上，图侵删)
所以
我们要实现这个邻接矩阵，在这里用的是二维数组 e[][]。
int e[510][510];//e[][]是唯一的二维数组，表示图的邻接矩阵fill(e[0], e[0] + 510 * 510, inf);
同时，在初始化的时候，根据手绘步骤，我们会把所有的距离先初始化为无穷大，在代码中用
const int inf = 99999999;
表示。
而后
继续考虑，访问过的点不应该再访问，所以用一个visit[]数组去标识它。
bool visit[510];//visit[]是一个布尔变量，记录顶点是否被访问，被访问则为true，初值为false表示还没有被访问
每一次的计算路径，也需要一个dis[]数组来存储该点到起点的最短路径。
int dis[510];//dis[]记录最短距离
fill(dis, dis + 510, inf);
接着
就是通过for循环来找到每个点的最短路径了。
下面通过简单代码来表示结构：
for(...i < n...){
u = -1, shortest = INF; //u作为每一行的起点，由于不知道是哪个所以初始化为-1；shortest表示起点u到下个点的最短距离
for(...j < n...){ //这个for循环是为了筛选出目前这一行（邻接矩阵图的行）中的最短路径的点，以此作为下一次的起点。
if(visited[j] == false && dis[j] < shortest){
shortest = dis[j];
u = j;
}// 这个if语句是用来判断j点是否被拜访过，通过dis[j]找出最短的距离的点j，以此使 u = j作为起点
}
visited[u] = true;//标记u为拜访过，下一次循环就不会找它了
for(...v < n...){ //这个for循环是为了找到这一行中对于起点u可连通的各个点的最短距离
if(visit[v] == false && e[u][v] != INF)//v点未被拜访过（没有循环过，没有做为过起点的意思，现在作为终点来计算）；且uv两点可连通。
{
if(dis[u] + e[u][v] < dis[v])
//以u为中介点时能令d[v]变小，比如一个三角形的图
//e.g. a到b,可直达为5，也可经过c（ac=2，cb=2）
//原本已知：dis[b] = 5
//在循环中发现：e[c][b] = 2, dis[c] = 2;
//所以可以更新: dis[b] = 4
{
dis[v] =
num[v] =
w[v] =
}
else if(dis[u] + e[u][v] == dis[v])
//如果路径长度相同，就看权重谁大，那就选谁
{
num[v] =
if(w[u] + weight[v] > w[v])
//以u为中介点时点权之和更大
{
w[v] =
}
}
}
}
}
知识点：
1.fill()函数
fill函数的作用是：将一个区间的元素都赋予val值。
函数参数：fill(first,last,val); //first为容器的首迭代器，last为容器的尾迭代器，
举例：
fill() 初始化二维数组 f[N][N]
fill(f[0], f[0]+N*N, k); k就是要填充的值，初始化的值。（👆上面代码中也用fill()初始化了两个数组）
Dijkstra代码写法总结：
Step 1：初始化
>上述分析过用来画图都要初始化
Step 2：for循环
>1.找出该行的起点
>2.找出起点到其他点的最短距离
>3.循环下一行，重复1,2步
网友评论