2492. Minimum Score of a Path Between Two Cities

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.

The score of a path between two cities is defined as the minimum distance of a road in this path.

Return the minimum possible score of a path between cities 1 and n.

Note:

• A path is a sequence of roads between two cities.
• It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
• The test cases are generated such that there is at least one path between 1 and n.

class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> adj(n + 1);
        for(auto r : roads) {
            int u = r[0], v = r[1], w = r[2];
            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }
        vector<int> vis(n + 1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({INT_MAX, 1});
        while(q.size()) {
            auto [w,u] = q.top(); q.pop();
            if(vis[u] != w) continue;
            for(auto [v,c] : adj[u]) {
                int cost = min(c,vis[u]);
                if(vis[v] > cost) {
                    vis[v] = cost;
                    q.push({cost,v});
                }
            }
        }
        if(vis[n] == INT_MAX) return -1;
        return vis[n];
    }
};