dijkstra_bin_heap.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const double INF = 1e18;

vector<pair<int, double>> adj[MAXN];
double dis[MAXN];
int n, m;

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

    freopen("data.txt", "r", stdin);

    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        int id;
        double x, y;
        cin >> id >> x >> y;
    }

    for(int i = 0; i < m; i++) {
        int u, v;
        double w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); 
    }

    int s = 0;
    for(int i = 0; i < n; i++) dis[i] = INF;
    dis[s] = 0;

    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    pq.push({0, s});

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

        if(d > dis[u]) continue;

        for(auto e : adj[u]) {
            int v = e.first;
            double w = e.second;
            if(dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }

    if(dis[n-1] == INF) cout << -1 << endl;
    else cout << fixed << setprecision(2) << dis[n-1] << endl;

    return 0;
}