题目链接：1003 Emergency

思路

这道题的难度超过了我的实力太多了，看着胡凡的算法笔记，刚了两天才刚过了。。。

首先，这是个正权无向图找最短路径的问题，额外要求是记录最短路径数，以及最短路径中次权最大为多少。考虑顶点较少（<1000，本题为500），同时我没写过图的算法，选择用邻接矩阵表示图，比较简单，其中设置一个大数INF表示无法到达。找最短路径基于Dijkstra算法。为了满足额外要求，增设两个数组保存每个顶点当前最短路径数，及符合最短路径要求下的最大次权大小。算法细节： Dijkstra： d数组，保存起始点到该点的最小距离，初始填充INF。vis数组，表示顶点是否已被纳入最短路径。将起始点距离设为0。遍历n轮，每轮从d数组中找到最小的，且连通的即小于INF的，且未被纳入最短路径的点作为当前点，若找不到说明剩余点不连通，退出循环，纳入后修改vis数组。以当前点为中心，遍历到所有点的距离，若到当前点的最短距离加上当前点到遍历点的距离小于遍历点的最短距离，修改遍历点的d数组。遍历完成后，d数组中存放各点的最短距离大小。以满足题目额外要求的补充算法： 初始时各点最短路径数均为0，次权也为0。将初始点最短路径数设为1，次权设为初始顶点人手数。遍历过程中，优化d数组时，将到遍历点的最短路径数置为当前点的最短路径数，人手数置为当前点加遍历点的人手数。若发现有路径长度相等的情况，将两点最短路径数相加，人手取大值。遍历结束后，即得到到各顶点最短路径数，与符合最短路径情况下最大人手数。

代码

（起名什么的最麻烦了）

#include <iostream> #include <vector> #include <algorithm> using namespace std; #define MAXV 500 #define INF 100000000 int n, minum[MAXV], G[MAXV][MAXV], hand[MAXV], handnow[MAXV];//保存城市数，最短路径数，距离，人手 int d[MAXV];//保存到达指定城市的距离 bool vis[MAXV] = {false};//是否访问过 void Dijkstra(int s){ fill(d, d + MAXV, INF); fill(minum, minum + MAXV, 0); fill(handnow, handnow + MAXV, 0); d[s] = 0; minum[s] = 1; handnow[s] = hand[s]; for(int i = 0; i < n; i++){ int u = -1, MIN = INF; //选出当前路径最小的点为u，若不存在说明剩余点不连通 for(int j = 0; j < n; j++){ if(!vis[j] && d[j]<MIN){ u = j; MIN = d[j]; } } if(u == -1) return; vis[u] = true; //优化d[u]表，hn[u]表 for(int v=0;v<n;v++){ if(!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]){ d[v] = d[u] + G[u][v]; minum[v] = minum[u]; handnow[v] = handnow[u] + hand[v]; } else if(d[u] + G[u][v] == d[v]){ minum[v] += minum[u]; if(hand[v] + handnow[u] > handnow[v]){ handnow[v] = hand[v] + handnow[u]; } } } } } int main(){ int M, C1, C2, a, b, c; cin >> n >> M >> C1 >> C2; for(int i=0;i<n;i++) cin >> hand[i]; fill(G[0], G[0] + MAXV * MAXV, INF); for(int i=0;i<M;i++){ cin >> a >> b >> c; G[a][b] = G[b][a] = c; } Dijkstra(C1); cout << minum[C2] << " " << handnow[C2]; return 0; }