Submission #1090600

#TimeUsernameProblemLanguageResultExecution timeMemory
1090600Octa_pe_infoCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
239 ms36696 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <climits> #include <bits/stdc++.h> using namespace std; // Structure to represent an edge in the graph struct Edge { int to; long long cost; }; // Custom comparator for the priority queue struct State { int node; long long dist; bool operator>(const State& other) const { return dist > other.dist; } }; const long long INF = LLONG_MAX; // Function to find a shortest path from S to T and return the edges used vector<pair<int, int>> find_shortest_path(int S, int T, int n, vector<vector<Edge>>& graph) { vector<long long> dist(n + 1, INF); vector<int> parent(n + 1, -1); priority_queue<State, vector<State>, greater<State>> pq; dist[S] = 0; pq.push({S, 0}); while (!pq.empty()) { State current = pq.top(); pq.pop(); int u = current.node; if (current.dist > dist[u]) continue; for (Edge& edge : graph[u]) { int v = edge.to; long long new_dist = dist[u] + edge.cost; if (new_dist < dist[v]) { dist[v] = new_dist; parent[v] = u; pq.push({v, new_dist}); } } } // Reconstruct the path from S to T vector<pair<int, int>> path_edges; int node = T; if (parent[node] == -1) { // No path found return path_edges; } while (parent[node] != -1) { int u = parent[node]; int v = node; path_edges.push_back({u, v}); node = u; } // The path is from T to S, reverse it reverse(path_edges.begin(), path_edges.end()); return path_edges; } // Function to calculate the minimum cost from U to V using the modified graph long long calculate_min_cost(int U, int V, int n, vector<vector<Edge>>& graph) { vector<long long> dist(n + 1, INF); priority_queue<State, vector<State>, greater<State>> pq; dist[U] = 0; pq.push({U, 0}); while (!pq.empty()) { State current = pq.top(); pq.pop(); int u = current.node; if (current.dist > dist[u]) continue; for (Edge& edge : graph[u]) { int v = edge.to; long long new_dist = dist[u] + edge.cost; if (new_dist < dist[v]) { dist[v] = new_dist; pq.push({v, new_dist}); } } } return dist[V]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; int S, T; cin >> S >> T; int U, V; cin >> U >> V; vector<vector<Edge>> graph(N + 1); // Read the graph for (int i = 0; i < M; ++i) { int A, B; long long C; cin >> A >> B >> C; graph[A].push_back({B, C}); graph[B].push_back({A, C}); } // Find a shortest path from S to T vector<pair<int, int>> shortest_path_edges = find_shortest_path(S, T, N, graph); if (shortest_path_edges.empty()) { // No path from S to T cout << "0\n"; return 0; } // Create a modified graph where edges along the path have cost zero vector<vector<Edge>> modified_graph = graph; // Create a set for quick lookup set<pair<int, int>> path_edge_set; for (auto& edge : shortest_path_edges) { int u = edge.first; int v = edge.second; path_edge_set.insert({u, v}); path_edge_set.insert({v, u}); // Since the graph is undirected } // Modify the edge costs along the path to zero for (int u = 1; u <= N; ++u) { for (Edge& edge : modified_graph[u]) { int v = edge.to; if (path_edge_set.count({u, v})) { edge.cost = 0; } } } // Calculate the minimum cost from U to V using the modified graph long long min_cost = calculate_min_cost(U, V, N, modified_graph); cout << min_cost << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...