Flowery Trails

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define F first
#define S second
vector<pair<ll, ll> > v[1010101];
ll dist1[1010101];
ll dist2[1010101];
int main() {
	int n,m;
	cin>>n>>m;
	priority_queue<pair<int, int> > qu;
	for(int i = 0; i < m; ++i) {
		int a,b,c;
		cin>>a>>b>>c;
		if(a != b) {
			v[a].push_back({b, c});
			v[b].push_back({a, c});
		}
	}
	for(int i = 0; i < 1010101; ++i) {
		dist1[i] = 1e18;
		dist2[i] = 1e18;
	}
	dist1[1] = 0;
	qu.push({0, 1});
	while(qu.size()) {
		auto x = qu.top();
		qu.pop();
		int node = x.S;
		for(auto y: v[node]) {
			ll nd = -x.F + y.S;
			ll np = y.F;
			if(dist1[np] > nd) {
				dist1[np] = nd;
				qu.push({-nd, np});
			}
		}
	}
	qu.push({0, n});
	dist2[n] = 0;
	while(qu.size()) {
		auto x = qu.top();
		qu.pop();
		int node = x.S;
		for(auto y: v[node]) {
			ll nd = -x.F + y.S;
			ll np = y.F;
			if(dist2[np] > nd) {
				dist2[np] = nd;
				qu.push({-nd, np});
			}
		}
	}
	ll sum = 0;
	for(int i = 1; i <= n; ++i) {
		for(auto y: v[i]) {
			if(dist1[i] < dist1[y.F]) {
				ll a = dist1[i];
				ll b = dist2[y.F];
				if(a + b + y.S == dist1[n]) sum += y.S;
			}
		}
	}
	cout<<sum*2<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED