Flowery Trails

input/code.cpp: In function 'int main()':
input/code.cpp:25:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v[cur].size(); ++i){
                                  ^

#include <bits/stdc++.h>

using namespace std;
vector<pair<int, int64_t>> v[101010];
vector<pair<int, int64_t>> sh[101010];
int main(){
	int n, m; cin >>  n >> m;
	for(int i = 0; i < m; ++i){
		int a, b, c; cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}
	set<pair<int64_t, int>> pq;
	pq.insert({0, 1});
	bool d[101010] = {0};
	vector<int64_t> dis(n+1, 2000000000L);
	while(!pq.empty()){
		int cur = (*pq.begin()).second;
		int64_t dist = (*pq.begin()).first;
		pq.erase(pq.begin());
		if(d[cur])
			continue;
		d[cur] = 1;
		dis[cur] = dist;
		for(int i = 0; i < v[cur].size(); ++i){
			auto f = v[cur][i];
			if(dist+f.second < dis[f.first]){
				dis[f.first] = dist+f.second;
				sh[f.first].clear();
				sh[f.first].push_back({cur, i});
			}
			else if(dist+f.second == dis[f.first]){
				sh[f.first].push_back({cur, i});
			}
			pq.insert({dist+f.second, f.first});
		}
	}
	queue<int> q;
	q.push(n);
	int64_t ans = 0;
	bool d2[101010] = {0};
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		if(d2[cur])
			continue;
		d2[cur] = 1;
		for(auto f: sh[cur]){
			q.push(f.first);
			ans+=v[f.first][f.second].second*2;
		}
	}
	cout << ans << "\n";
	return 0;
}

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