C++算法题解：城市旅游地图派送与最短路径安全道路数量最大化

问题描述

在一个由 n 个路口和 m 条道路构成的城市中，每条道路长度相同。需要选择一个路口派送旅游地图给游客，目标是使得从起点(路口1)到终点(路口n)的所有最短路径中，经过所选路口且该路口不是起点或终点时，安全道路的数量平均值最大化。

安全道路的定义： 一条道路是安全的，当且仅当这条道路的两端中恰好有一个路口是你选择的路口。

输入

第一行输入两个整数 n, m，分别表示路口和道路的数量 (2 <= n <= 100, n-1 <= m <= n*(n-1)/2)。* 接下来 m 行，每行两个整数 u, v，表示一条双向道路 (1 <= u, v <= n)。* 保证没有重边，且任意两个路口是可达的。

输出

输出一个浮点数，表示安全道路数量的最大平均值，误差不超过 10^(-6)。

解题思路

使用 Dijkstra 算法计算最短路径： 首先，利用 Dijkstra 算法计算从起点到每个路口的距离，以及从每个路口到终点的距离。
遍历每个路口计算安全道路数量： 遍历每个路口，计算经过该路口的最短路径数量。对于每个路口，将从起点到该路口的距离与从该路口到终点的距离相加，如果该距离等于起点到终点的最短路径长度，则说明该路口在某条最短路径上。
计算安全道路平均值并更新最大值： 对于每个路口，计算经过该路口的最短路径上安全道路的数量，并累加到总安全道路数量中。最后，将总安全道路数量除以最短路径的数量，即可得到平均值。

C++ 代码实现cpp#include #include #include #include

using namespace std;

const double INF = numeric_limits::infinity();

struct Edge { int to; double weight;};

vector dijkstra(int start, int n, const vector<vector>& graph) { vector dist(n + 1, INF); dist[start] = 0.0;

priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;    pq.push({0.0, start});

while (!pq.empty()) {        double d = pq.top().first;        int u = pq.top().second;        pq.pop();

    if (d > dist[u]) {            continue;        }

    for (const Edge& edge : graph[u]) {            int v = edge.to;            double w = edge.weight;

        if (dist[u] + w < dist[v]) {                dist[v] = dist[u] + w;                pq.push({dist[v], v});            }        }    }

return dist;}

double calculateAverageSafety(int n, const vector<vector>& graph) { double totalSafety = 0.0; vector distFromStart = dijkstra(1, n, graph); vector distToEnd = dijkstra(n, n, graph);

for (int i = 2; i < n; ++i) {        if (distFromStart[i] + distToEnd[i] == distFromStart[n]) {            totalSafety += 2.0;        }    }

return totalSafety / (n - 2);}

int main() { int n, m; cin >> n >> m;

vector<vector<Edge>> graph(n + 1);

for (int i = 0; i < m; ++i) {        int u, v;        cin >> u >> v;        graph[u].push_back({v, 1.0});        graph[v].push_back({u, 1.0});    }

double averageSafety = calculateAverageSafety(n, graph);    cout << fixed;    cout.precision(9);    cout << averageSafety << endl;

return 0