Shared code

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define int ll
#define endl '\n'
 
const ll mod = 1000000007;
const int inf = INT64_MAX;
 
signed main()
{
    int n, m;
    cin >> n >> m;
 
    unordered_map<int, vector<pair<int, int>>> graph;
 
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
    }
 
    vector<vector<int>> dist(n + 1, vector<int>(2, inf));
 
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push(make_tuple(0, 1, 0));
 
    while (!pq.empty())
    {
        int cur_dist, city, used;
        tie(cur_dist, city, used) = pq.top();
        pq.pop();
 
        if (cur_dist > dist[city][used])
        {
            continue;
        }
 
        for (const auto &neighbor : graph[city])
        {
            int v = neighbor.first;
            int w = neighbor.second;
 
            if (used == 0)
            { // try using the ticket
                int new_cost = cur_dist + w / 2;
                if (new_cost < dist[v][1])
                {
                    dist[v][1] = new_cost;
                    pq.push(make_tuple(new_cost, v, 1));
                }
            }
 
            int new_cost = cur_dist + w;
            if (new_cost < dist[v][used])
            {
                dist[v][used] = new_cost;
                pq.push(make_tuple(new_cost, v, used));
            }
        }
    }
 
    cout << dist[n][1] << endl;
 
    return 0;
}