Submission #9155555

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#define int long long
#define mod 1000000007
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define F first
#define S second
#define P pair<int,int>
using namespace std;
bool x[200000];
int xs[200000],xw[200000];
vector<pair<P,int>> vs[200000], vw[200000];
priority_queue<P, vector<P>, greater<P>> q1, q2;
int mutu(int va,bool s,bool w) {
	if (!va) return 1;
	int ans = 0;
	for0(i, vs[va].size()) {
		bool bs = false, bw = false;
		if (s&&(xs[vs[va][i].first.first] == (xs[va] - vs[va][i].first.second)))bs = true;
		if (w&&(xw[vw[va][i].first.first] == (xw[va] - vw[va][i].first.second)))bw = true;
		if(bs||bw){
			ans+=mutu(vs[va][i].first.first,bs,bw);
		}
	}
	return ans;
}
int mu2(int va) {
	if (!va) return 1;
	int ans = 0;
	for0(i, vw[va].size()) {
		if (xw[vw[va][i].first.first] == xw[va] - vw[va][i].first.second) {
			x[vw[va][i].second] = true;
			ans+=mu2(vw[va][i].first.first);
		}
	}
	return ans;
}
signed main(){
	int a, b, ans = 0;
	cin >> a >> b;
	for0(i, b) {
		int va, vb, vc, vd;
		cin >> va >> vb >> vc >> vd;
		va--, vb--;
		vs[va].push_back({ { vb,vc },i });
		vs[vb].push_back({ { va,vc },i });
		vw[va].push_back({ { vb,vd },i });
		vw[vb].push_back({ { va,vd },i });
	}
	for0(i, a) {
		xs[i] = 100000000000;
		xw[i] = 100000000000;
	}
	xs[0] = 0;
	xw[0] = 0;
	q1.push({ 0,0 });
	while (q1.size()) {
		P p = q1.top();
		q1.pop();
		if (xs[p.second] < p.first) continue;
		for0(i, (int)vs[p.second].size()) {
			if (xs[vs[p.second][i].first.first] > p.first + vs[p.second][i].first.second) {
				xs[vs[p.second][i].first.first] = p.first + vs[p.second][i].first.second;
				q1.push({ p.first + vs[p.second][i].first.second, vs[p.second][i].first.first });
			}
		}
	}
	q2.push({ 0,0 });
	while (q2.size()) {
		P p = q2.top();
		q2.pop();
		if (xw[p.second] < p.first)continue;
		for0(i, (int)vw[p.second].size()) {
			if (xw[vw[p.second][i].first.first] > p.first + vw[p.second][i].first.second) {
				xw[vw[p.second][i].first.first] = p.first + vw[p.second][i].first.second;
				q2.push({ p.first + vw[p.second][i].first.second, vw[p.second][i].first.first });
			}
		}
	}
	cout << mutu(a-1,true,true) << endl;
}

Submission Info

Judge Result