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;
vector<vector< pair<int,int>> > adjList;
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;
for(auto &pr : adjList[u]) {
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);
adjList.resize(n+3);
int u, v, w;
while(m–) {
scanf(“%d %d %d”, &u, &v, &w);
adjList[u].push_back(pair<int,int> (v, w));
adjList[v].push_back(pair<int,int> (u, w));
}
if(dijkstra(1, n)) {
vector path;
for(v = n; v != -1; v = par[v]) path.push_back(v);
for(int i = path.size()-1; i > 0; --i) printf(“%d “, path[i]);
printf(”%d\n”, path[0]);
}
else puts("-1");
return 0;
}