题目

假设你是一个城市的紧急救援队队长，你会得到一张你国家的特别地图。当有紧急电话从其他城市打给你时，你的工作是尽快带你的人到那个地方，同时，在路上尽可能多地召集人手。
输入的数：

行数	数字	含义
第一行	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步