# CodeForces - Problem C - Contest 20

Hello developers of CodeChef! I am stuck on this question (Contest 20, problem C)- WA on test case 31 and I do not know why!

For this problem, I used Dijkstra’s algorithm to traverse the graph. Then using a hashmap to store previous nodes (the path), we can finally print out the path, given the destination node is reachable from the start node.

``````#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <limits.h>

typedef unsigned long long ull;

using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n, m;
cin >> n >> m;

// Get the adjacency list and mapping to previous elements
map<int, int> prev;

while (m--) {
int u, v;
uint64_t w;
cin >> u >> v >> w;

prev[u-1] = -1;
prev[v-1] = -1;
}

// Create a list of distances and visited nodes
vector<bool> seen(n, false);
vector<uint64_t> dist(n, UINT_MAX);

dist[0] = 0;

// Create the priority queue
priority_queue<pair<uint64_t, int>> pq;
pq.push({0, 0});

while (!pq.empty()) {
int u = pq.top().second;
pq.pop();

// Check if the node has already been visited
if (seen[u]) {
continue;
}

seen[u] = true;

// Check if the node is the destination
if (u == n-1) {
break;
}

// Go through the neighbor nodes
for (pair<int, uint64_t> v : adj[u]) {
// Check if the distance is minimal
if (dist[u] + v.second < dist[v.first]) {
prev[v.first] = u;
dist[v.first] = dist[u] + v.second;

pq.push({-dist[v.first], v.first});
}
}
}

// Check if the destination node is reachable
if (dist[n-1] == UINT_MAX) {
cout << -1;
return 0;
}

// Traverse the shortest path
int key = n-1;
vector<int> path;

while (key != -1) {
path.push_back(key);
key = prev[key];
}

while (!path.empty()) {
cout << path.back() + 1 << " ";
path.pop_back();
}
}
``````

I would greatly appreciate if you could help me in any way, thank you!