#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; struct Edge { int to; int cost; int reverse_idx; }; vector<vector<Edge>> adj; // 邻接表存储图 // Dijkstra算法求最短路径，同时记录路径 pair<int, vector<int>> dijkstra(int start, int end, const vector<pair<int, int>>& forbidden) { int n = adj.size(); vector<int> dist(n, INT_MAX); vector<int> prev(n, -1); vector<int> edge_idx(n, -1); // 记录到达节点i的边在adj[prev[i]]中的索引 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; int d = pq.top().first; pq.pop(); if (u == end) break; if (d > dist[u]) continue; for (int i = 0; i < adj[u].size(); ++i) { const Edge& e = adj[u][i]; // 检查是否为禁止的边 bool is_forbidden = false; for (const auto& f : forbidden) { if (f.first == u && f.second == e.to) { is_forbidden = true; break; } } if (is_forbidden) continue; if (dist[e.to] > dist[u] + e.cost) { dist[e.to] = dist[u] + e.cost; prev[e.to] = u; edge_idx[e.to] = i; pq.push({dist[e.to], e.to}); } } } // 构建路径 vector<int> path; if (dist[end] == INT_MAX) return {INT_MAX, path}; int current = end; while (current != start) { path.push_back(current); current = prev[current]; } path.push_back(start); reverse(path.begin(), path.end()); return {dist[end], path}; } int main() { int n, m; cin >> n >> m; adj.resize(n + 1); // 1-based indexing for (int i = 0; i < m; ++i) { int u, v, cost; cin >> u >> v >> cost; adj[u].push_back({v, cost, (int)adj[v].size()}); adj[v].push_back({u, cost, (int)adj[u].size() - 1}); // 记录反向边的索引 } int a, b; cin >> a >> b; // 第一次Dijkstra：从a到b vector<pair<int, int>> forbidden; auto [cost1, path1] = dijkstra(a, b, forbidden); if (cost1 == INT_MAX) { cout << -1 << endl; return 0; } // 构建禁止的边集（去程使用的边的反向边） for (int i = 0; i < path1.size() - 1; ++i) { int u = path1[i]; int v = path1[i + 1]; forbidden.push_back({v, u}); // 禁止反向边 } // 第二次Dijkstra：从b到a，避开禁止的边 auto [cost2, path2] = dijkstra(b, a, forbidden); if (cost2 == INT_MAX) { cout << -1 << endl; return 0; } cout << cost1 + cost2 << endl; return 0; }