Shortest Routes I

#include <bits/stdc++.h>

using namespace std;

//Definitions for quicker writing
#define REP(i,a,b) for (int i = a; i < b; i++)

//Typedefs for quicker writing
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

//Max values
const long long lmx = LLONG_MAX;
const int imx = INT_MAX;

int main() {
	//IO optimization
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//Input definition
	int n;
	int m;

	//Read In
	cin >> n >> m;
	
	//Init adj list
	vector<vector<pair<ll, ll>>> adj(n+1);	
	
	REP(i,0,m){
		ll a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
	}
	
	//Init distances
	vector<ll> dist(n+1,lmx);
	dist[1] = 0;

	//Init processed
	vector<bool> proc(n+1,false);

	//Init priority queue
	priority_queue<pair<ll,ll>> q;
	q.push({0,1});

	//Dijkstra
	while(!q.empty()){
		ll cur = q.top().second;
		q.pop();
		if(proc[cur]) continue;
		proc[cur] = true;
		for(auto neigh : adj[cur]){
			ll next = neigh.first;
		       	ll w = neigh.second;
			if(dist[cur]+w < dist[next]){
				dist[next] = dist[cur] + w;
				q.push({-dist[next], next});
			}
		}
	}
	

	//Write out
	REP(i,1,n+1){
		cout << dist[i] << " ";
	}

	cout << endl;

	//Return
	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

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED