제출 #1090602

#제출 시각아이디문제언어결과실행 시간메모리
1090602Octa_pe_infoCommuter Pass (JOI18_commuter_pass)C++14
컴파일 에러
0 ms0 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 { long long to; long long cost; }; // Custom comparator for the priority queue struct State { long long 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<long long, long long>> find_shortest_path(long long S, long long T, long long n, vector<vector<Edge>>& graph) { vector<long long> dist(n + 1, INF); vector<long long> 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(); long long u = current.node; if (current.dist > dist[u]) continue; for (Edge& edge : graph[u]) { long long 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<long long, long long>> path_edges; long long node = T; if (parent[node] == -1) { // No path found return path_edges; } while (parent[node] != -1) { long long u = parent[node]; long long 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(long long U, long long V, long long 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(); long long u = current.node; if (current.dist > dist[u]) continue; for (Edge& edge : graph[u]) { long long 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]; } long long main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long N, M; cin >> N >> M; long long S, T; cin >> S >> T; long long U, V; cin >> U >> V; vector<vector<Edge>> graph(N + 1); // Read the graph for (long long i = 0; i < M; ++i) { long long 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<long long, long long>> 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<long long, long long>> path_edge_set; for (auto& edge : shortest_path_edges) { long long u = edge.first; long long 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 (long long u = 1; u <= N; ++u) { for (Edge& edge : modified_graph[u]) { long long 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; }

컴파일 시 표준 에러 (stderr) 메시지

cc1plus: error: '::main' must return 'int'