# HW3G - Editorial

Practice
Source

Author: SQU_Test

DIFFICULTY:
Medium

PREREQUISITES:
Graph, Shortest Path, Dijkstra.

PROBLEM:
You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between vertex 1 and vertex n.

EXPLANATION:
To solve this problem, you need to implement the Dijkstra algorithm using priority queue.

TIME COMPLEXITY:
Time complexity of the solution is O(n log n).

SOLUTIONS:

Setter’s Solution
``````#include <cstdio>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
const int MAXN = 1e5 + 3;
const int INF = INT_MAX;

int n, dist[MAXN], par[MAXN];
bitset<MAXN> isDone;

bool dijkstra(int s, int t)
{
``````

priority_queue< pair<int,int>, vector< pair<int,int>>, greater< pair<int,int>> > pq;
fill(dist, dist+n+1, INF);
pq.push(pair<int,int> (0, s));
dist[s] = 0;
par[s] = -1;

``````	while(!pq.empty()) {
``````

int u = pq.top().second; pq.pop();
if(u == t) return true;
isDone[u] = true;
int v = pr.first, w = pr.second;
if(!isDone[v] && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push(pair<int,int> (dist[v], v));
par[v] = u;
}
}
}
return false;

``````}
int main()
{
int m;
``````

scanf("%d %d", &n, &m);
int u, v, w;
while(m–) {
scanf("%d %d %d", &u, &v, &w);
``````    }