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