Submission #1090603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090603		Octa_pe_info	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	211 ms	35784 KiB

commuter_pass

#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];
}

int 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;
}

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45