本文共 2922 字，大约阅读时间需要 9 分钟。
为了解决这个问题，我们需要找到哈利波特从城市1到城市n的最短路径，并在考虑伏地魔破坏任意一条边的情况下，确保哈利波特仍能以最坏情况下的最短时间到达城市n。
方法思路
计算最短路径：首先，我们使用Dijkstra算法计算从城市1到所有其他城市的最短距离，存储在数组d1中。 收集最短路径边：接下来，我们收集所有属于最短路径的边，这些边满足d1[u] + w == d1[v]或d1[v] + w == d1[u]，其中u和v是边的两个端点。 破坏每条最短路径边：对于每条收集到的最短路径边，我们模拟破坏这条边，然后重新计算破坏后的最短路径。 计算破坏后的最短路径：在破坏一条边后，使用Dijkstra算法重新计算从城市1到城市n的最短路径，记录破坏后的最短路径时间。 确定最大时间：在所有破坏情况下，找出破坏后的最短路径时间的最大值。如果所有破坏情况下都无法到达城市n，则输出-1。 解决代码
#include #include #include #include using namespace std;struct Edge { int u, v, w; int id;};void add_edge(int u, int v, int w, int id, vector >& adj) { adj[u].push_back({v, w, id}); adj[v].push_back({u, w, id});}void dijkstra(int start, int n, int exclude_u, int exclude_v, int exclude_w, vector >& adj, vector & dist) { dist.assign(n + 1, INT_MAX); dist[start] = 0; priority_queue > pq; pq.push({0, start}); while (!pq.empty()) { int d, u = pq.top().second; pq.pop(); if (dist[u] < d) continue; for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; int edge_id = edge.third; // 跳过被破坏的边 if (u == exclude_u && v == exclude_v && w == exclude_w) { continue; } if (v == u) continue; // 防止自环 if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } }}int main() { int t; cin >> t; for (int _ = 0; _ < t; ++ _) { int n, m; cin >> n >> m; vector > adj(n + 1); vector all_edges; for (int i = 0; i < m; ++ i) { int u, v, w; cin >> u >> v >> w; all_edges.push_back({u, v, w}); add_edge(u, v, w, i, adj); } vector d1(n + 1, INT_MAX); d1[1] = 0; priority_queue > pq; pq.push({0, 1}); while (!pq.empty()) { int d, u = pq.top().second; pq.pop(); if (d1[u] < d) continue; for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (d1[v] > d1[u] + w) { d1[v] = d1[u] + w; pq.push({d1[v], v}); } } } if (d1[n] == INT_MAX) { cout << "-1"; continue; } vector E_prime; for (int i = 0; i < m; ++ i) { const Edge& e = all_edges[i]; if (d1[e.u] + e.w == d1[e.v]) { E_prime.push_back(i); } } vector dist_n_list; for (int e_id : E_prime) { const Edge& e = all_edges[e_id]; vector dist(n + 1, INT_MAX); dist[1] = 0; priority_queue > pq; pq.push({0, 1}); while (!pq.empty()) { int d, u = pq.top().second; pq.pop(); if (dist[u] < d) continue; for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; int edge_id = edge.third; if (u == e.u && v == e.v && w == e.w) { continue; } if (v == u) continue; if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } } if (dist[n] != INT_MAX) { dist_n_list.push_back(dist[n]); } } if (dist_n_list.empty()) { cout << "-1"; } else { int max_time = *max_element(dist_n_list.begin(), dist_n_list.end()); cout << max_time; } } return 0;}
代码解释
读取输入：读取测试用例的数量和每个测试用例的城市数和边数。 建立邻接表：读取每条边并构建邻接表。 计算最短距离：使用Dijkstra算法计算从城市1到所有其他城市的最短距离。 收集最短路径边：收集所有属于最短路径的边。 破坏每条最短路径边：对每条收集到的最短路径边，模拟破坏后重新计算最短路径。 记录破坏后的最短路径时间：记录破坏后的最短路径时间，找出最大值并输出结果。 转载地址：http://hrewz.baihongyu.com/