QBSCHOOL - Đến trường

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

using namespace std;

const int N = 5050;
const int INF = 1e9;

struct Edge {
    int to, cost;
    Edge(int to, int cost): to(to), cost(cost) {}
};

namespace PriorityQueue {
    static const int LIMIT = 2e5;
    vector<int> V[LIMIT];
    int size;
    int cur;

    void push(int u, int d) { V[d].push_back(u); ++size; }
    void getMin(int &u, int &du) {
        while (cur < LIMIT && V[cur].empty()) ++cur;
        assert(cur < LIMIT);
        --size;
        u = V[cur].back(); du = cur;
        V[cur].pop_back();
    }
}

int d[N];
long long cnt[N];;
int n, m;

vector<Edge> a[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int k, u, v, L;
        cin >> k >> u >> v >> L;
        a[u].push_back(Edge(v, L));
        if (k == 2) a[v].push_back(Edge(u, L));
    }
    for (int i = 2; i <= n; ++i) d[i] = INF;
    PriorityQueue::push(1, 0); cnt[1] = 1;
    while (PriorityQueue::size) {
        int u, du;
        PriorityQueue::getMin(u, du);
        if (d[u] != du) continue;
        for (auto e : a[u]) {
            int v = e.to;
            int c = e.cost;
            if (d[v] > d[u] + c) {
                d[v] = d[u] + c;
                PriorityQueue::push(v, d[v]);
                cnt[v] = cnt[u];
            } else if (d[v] == d[u] + c) {
                cnt[v] += cnt[u];
            }
        }
    }
    cout << d[n] << ' ' << cnt[n] << endl;
    return 0;
}

Download