QBSCHOOL - Đến trường

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 30005
typedef long long LL;

int d[N], n, m;
LL c[N];
vvii g;

void dijkstra(vvii&g, int s, int *d, LL *c) {
	fill(d,d+n,INF); d[s] = 0; c[s] = 1;
	priority_queue< ii, vii, greater<ii> > qu;
	qu.push(ii(0,s));
	while(!qu.empty()) {
		int u = qu.top().se, du = qu.top().fi; qu.pop();
		if(du > d[u]) continue;
		tr(g[u],it) {
			int v = it->fi, l = it->se;
			if( du + l < d[v] ) {
				qu.push(ii(d[v] = du+l,v));
				c[v] = c[u];
			} else if( du + l == d[v] ) c[v] += c[u];
		}
	}
}

int main() {
	scanf("%d%d",&n,&m); g.resize(n);
	rep(i,m) {
		int k, u, v, l; scanf("%d%d%d%d",&k,&u,&v,&l);
		g[--u].pb(ii(--v,l));
		if(k == 2) g[v].pb(ii(u,l));
	}
	dijkstra(g, 0, d, c);
	printf("%d %lld\n", d[n-1], c[n-1]);
	return 0;
}

Download