还是那上面这张图举个例子，C1-C3的距离为2，而C1-C2的距离为4，4 > 2是既定事实，不管怎么走只要经过C2再绕回C3就不可能出现路径更短的情况！
for (int j = 0; j < N; j++) { // 找出没访问过的顶点中距离最近的点 if (!visit[j] && dis[j] < minn) { u = j; minn = dis[j]; } }然后我们再来寻找最短路径的最大数量以及救援队的数量。很显然，我们要先找到最短路径，方法就是用Dijkstra算法：遍历当前访问节点的所有邻接节点，如果路程比记录的路程更短，就覆盖原有数据：
if (dis[u] + edge[u][v] < dis[v]) { dis[v] = dis[u] + edge[u][v]; // 因为找到了有更短路程的路径，就用新的路径的条数覆盖原有的路径条数 roads[v] = roads[u]; teams[v] = teams[u] + weight[v]; }这里的u为当前访问节点，v为u的邻接节点。因为找到了更短的路，所以原本的路径都失效了，现在有效的路径是从u触发到v的路径，而根据题目的描述，两个城市之间只有一条路，所以上面的赋值语句实际含义为：
roads[v] = roads[u] * 1;如果有多条路径，那可以把1换成路径的数量。
而当路程等于最短路程时，就相当于新发现了一条路，并且由于每个节点仅仅访问一次，所以不会有重复的问题，不需要考虑去重。
else if (dis[u] + edge[u][v] == dis[v]) { // 如果v这个点没有被访问过，并且从起始点到v点的距离=从起始点到u再到v的距离 // 那就是说到相同的目的地，路程一样长，但是走过的路是不一样的，就把这些不同的路和原本的路径的数量相加。 roads[v] = roads[v] + roads[u]; if (teams[u] + weight[v] > teams[v]) { teams[v] = teams[u] + weight[v]; } }因为到下个节点v经过的路径每一条都是完全不同的，所以可以直接相加，并且也是因为俩城市只有一条路，所以实际含义为:
roads[v] = roads[v] + roads[u] * 1;如果这个最短路径能够携带的救援队数量比原来的要多，就更新原来的数据，因为最短路径都是一样长的，所以救援队并不需要考虑归属问题，我们只要求数量！
代码 #include <iostream> #include <vector> #include <limits.h> using namespace std; int main() { //读取第一行数据 int N, M, C1, C2; cin >> N >> M >> C1 >> C2; vector<int> weight(N, 0); for (int i = 0; i < N; i++) { cin >> weight[i]; } vector<vector<int>> edge(N, vector<int>(N, INT_MAX)); // 到i顶点的距离 vector<int> dis(N, INT_MAX); // c1和 c2之间不同的最短路径的数量 vector<int> roads(N, 0); // 到i顶点的救援队的数量 vector<int> teams(N, 0); // 是否访问过i顶点 vector<bool> visit(N, false); //初始化边权值表 int c1, c2, L; for (int i = 0; i < M; i++) { cin >> c1 >> c2 >> L; edge[c1][c2] = edge[c2][c1] = L; } dis[C1] = 0; teams[C1] = weight[C1]; roads[C1] = 1; for (int i = 0; i < N; ++i) { int u = -1, minn = INT_MAX; for (int j = 0; j < N; j++) { // 找出没访问过的顶点中距离最近的点 if (!visit[j] && dis[j] < minn) { u = j; minn = dis[j]; } } if (u == -1) break; visit[u] = true; for (int v = 0; v < N; v++) { // 如果v这个点没有访问过，且u到v是有路径的，那么就有可能刷新最短距离。 if (!visit[v] && edge[u][v] != INT_MAX) { if (dis[u] + edge[u][v] < dis[v]) { dis[v] = dis[u] + edge[u][v]; // 因为找到了有更短路程的路径，就用新的路径的条数覆盖原有的路径条数 roads[v] = roads[u]; teams[v] = teams[u] + weight[v]; } else if (dis[u] + edge[u][v] == dis[v]) { // 如果v这个点没有被访问过，并且从起始点到v点的距离=从起始点到u再到v的距离 // 那就是说到相同的目的地，路程一样长，但是走过的路是不一样的，就把这些不同的路和原本的路径的数量相加。 roads[v] = roads[v] + roads[u]; if (teams[u] + weight[v] > teams[v]) { teams[v] = teams[u] + weight[v]; } } } } } cout << roads[C2] << " " << teams[C2] << endl; return 0; }
https://zhuanlan.zhihu.com/p/138001717