dijkstra.cc

#include <iostream>
#include <vector>
#include <utility>
#include <functional>
#include <set>
#include <stack>
#include <queue>
using namespace std;

class CompareDist {
    public:
        bool operator()(pair<int,int> n1, pair<int,int> n2) {
            return n1.second>n2.second;
        }
};

void addEdge(vector<vector<pair<int,int>>> &graph, int a, int b, int weight) {
  graph[a].emplace_back(b,weight);
  graph[b].emplace_back(a,weight);
}


void dijkstra(vector<vector<pair<int,int>>> &graph){

    bool found = false;
    priority_queue<pair<int,int>, vector<pair<int,int>>, CompareDist> queue;
    int graphSize = graph.size();
    vector<long long> dist(graphSize, 2e18);
    vector<int> prev(graphSize, -1);

    queue.push({1,0});
    dist[1] = 0;

    while (!queue.empty()){

        int u = queue.top().first;
        queue.pop();

        if(u == graphSize - 1){
            found = true;
            break;
        }

        for(auto neighbor: graph[u]) {
            if (dist[u] + neighbor.second < dist[neighbor.first]){
                dist[neighbor.first] = dist[u] + neighbor.second;
                prev[neighbor.first] = u;
                queue.push({neighbor.first, dist[neighbor.first]});
            }
        }

    }

    if(found) {
        stack<int> path;
        int temp = graphSize - 1;
        while(temp != 1){
            path.push(temp);
            temp = prev[temp];
        } 
        path.push(1);
        while(!path.empty()){
            cout << path.top() << " ";
            path.pop();
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }

}

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

    int v, e;
    cin >> v >> e;
    vector<vector<pair<int,int>>> graph(v+1);
    for(int i = 0; i < e; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        addEdge(graph, a, b ,c);
    }

    dijkstra(graph);
    

    return 0;
}