Submission #74603239

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int inf = 1e18;
typedef pair<int,int> PII;
vector<vector<PII>> adj;
vector<int> dist;
vector<bool> st;
int n, m;
int Dijkstra(){
	
	dist[1] = 0;
	priority_queue<PII,vector<PII>,greater<PII>> heap;
	heap.push({0, 1});
	
	while(!heap.empty()){
		
		auto [_ , u] = heap.top();
		heap.pop();
		
		if(st[u])
			continue;
		
		st[u] = true;
		
		for(auto [v, w] : adj[u]){
			
			if(dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				heap.push({dist[v], v});
			}
		}
		
	}
	
	return dist[n] == inf ? -1 : dist[n];
}
signed main(){
	
	cin >> n >> m;
	adj.assign(n + 1, {});
	dist.assign(n + 1, inf);
	st.assign(n + 1, false);
	
	while(m -- ){
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		// adj[v].push_back({u, w});
	}
	
	cout << Dijkstra() << endl;
	
	return 0;
}

Submission Info

Judge Result