Submission #766121

#	Time	Username	Problem	Language	Result	Execution time	Memory
766121		OrazB	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	197 ms	18152 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const long long INF = numeric_limits<long long>::max();

struct Railway {
    int start;
    int end;
    long long fare;
};

struct Node {
    int station;
    long long cost;

    bool operator>(const Node& other) const {
        return cost > other.cost;
    }
};

long long findMinCost(const vector<vector<Railway>>& graph, int N, int S, int T, int U, int V) {
    vector<long long> dist(N + 1, INF);
    dist[S] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({S, 0});

    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();

        int station = node.station;
        long long cost = node.cost;

        if (cost > dist[station]) {
            continue;
        }

        for (const Railway& railway : graph[station]) {
            int nextStation = railway.end;
            long long fare = railway.fare;

            if (dist[station] + fare < dist[nextStation]) {
                dist[nextStation] = dist[station] + fare;
                pq.push({nextStation, dist[nextStation]});
            }
        }
    }

    long long minCost = INF;

    // Calculate the minimum cost from U to V considering all possible routes between S and T
    for (const Railway& railway1 : graph[U]) {
        for (const Railway& railway2 : graph[V]) {
            if (dist[railway1.start] + railway1.fare + dist[railway2.end] < minCost) {
                minCost = dist[railway1.start] + railway1.fare + dist[railway2.end];
            }
        }
    }

    return minCost;
}

int main() {
    int N, M;
    cin >> N >> M;

    int S, T;
    cin >> S >> T;

    int U, V;
    cin >> U >> V;

    vector<vector<Railway>> graph(N + 1);
    for (int i = 1; i <= M; i++) {
        int A, B;
        long long C;
        cin >> A >> B >> C;
        graph[A].push_back({A, B, C});
        graph[B].push_back({B, A, C});
    }

    long long minCost = findMinCost(graph, N, S, T, U, V);
    cout << minCost << endl;

    return 0;
}

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