Từ Trường THPT chuyên Lê Quý Đôn, Bình Định, Trường THPT chuyên Chu Văn An, Bình Định
Thông tin
! ! >! ! >! >! ! >! >! >! ! >! >! >! >! ! >! >! >! >! >! ! >! >! >! >! >! >! ! >! >! >! >! >! >! >! Nothing :D ! >! >! >! >! >! >! ! >! >! >! >! >! ! >! >! >! >! ! >! >! >! ! >! >! ! >! !
include <bits/stdc++.h>
define pb push_back
define ll long long
define fi first
define se second
define fu(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;
const int N = 5005;
const int inf = 1e9 + 5;
bool c[N];
int n, m, k, u, v, l;
int f[N];
ll d[N];
vector <pair
int main() { cin >> n >> m; while (m--) { cin >> k >> u >> v >> l; g[u].pb({v, l}); if (k == 2) g[v].pb({u, l}); } f[1] = 1; c[1] = 1; fu(i, 2, n) d[i] = inf, c[i] = 1; for (int o = n; o--; ) { int x = 0; fu(i, 1, n) if (c[i]) if (x == 0 || d[x] > d[i]) x = i; if (x == 0) break; if (x == n) break; c[x] = 0; for (pair <int, int> p: g[x]) { v = p.fi; l = p.se; if (d[v] > d[u] + l) { d[v] = d[u] + l; f[v] = f[u]; } else if (d[v] == d[u] + l) f[v] += f[u]; } } cout << d[n] << ' ' << f[n]; }