2492.两个城市间路径的最小分数

链接：2492.两个城市间路径的最小分数
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：城市 1 和城市 n 之间的所有路径的 最小 分数。

题解 1 - cpp

• 编辑时间：2022-12-04
• 执行用时：412ms
• 内存消耗：130.8MB
• 编程语言：cpp
• 解法介绍：因为同一条路可以走多次，且 1 和 n 一定存在路，遍历 1 出发的所有路，找到最小值即可。

#include <iostream>
#include <vector>
// bestlyg
# define X first
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeof(a))
# define debug freopen("r.txt","r",stdin)
# define pi pair<int,int>
#ifdef DEBUG
#define log(frm, args...) {    printf(frm, ##args); }
#else
#define log(frm, args...)
#endif
typedef long long ll;
using namespace std;
class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pi>> list(n);
        for (auto &road : roads) {
            int v1 = road[0] - 1, v2 = road[1] - 1;
            list[v1].push_back(make_pair(v2, road[2]));
            list[v2].push_back(make_pair(v1, road[2]));
        }
        int ans = 0x7fffffff;
        unordered_set<int> s;
        queue<int> q;
        q.push(0);
        s.insert(0);
        while (q.size()) {
            int cur = q.front();
            q.pop();
            for (auto &next : list[cur]) {
                ans = min(ans, next.Y);
                if (s.count(next.X)) continue;
                q.push(next.X);
                s.insert(next.X);
            }
        }
        return ans;
    }
};