G. Bicycles 分层图单源最短路

题目链接
简单描述一下题意：
给定n个点，m条带权无向边，每个点i有一辆速度系数为Si的自行车。每经过一个点即可拥有该点的自行车，在任意两点之间路过的消耗为：已经拥有的某辆自行车的速度Si * 边权Wi，求从1号点到n号点的最小消耗。

思路：
因为需要求的是最小的总消耗，所以在某个点出发时，我们所选用的自行车的S肯定是越小越好的，此处可以贪心考虑。
我们重构一下这个图，把到达每个点时的状态（即当前所拥有的最小的）也考虑进来，
组建一个新的节点u：<节点编号u，状态stateU = min(statePre, s[u])>
所有的u的可达节点v从原题目读入的可达路径中重构，
在加入状态表示以后变为：<节点编号v，状态stateV = min(stateU, s[v])>
此时再对重构图使用dijkstra即可，起点为<1号节点，s[1]>。

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    vector<int> s(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a - 1].push_back({b - 1, c});
        g[b - 1].push_back({a - 1, c});
    }
    for (auto &p : s) {
        cin >> p;
    }

    auto dijkstra = [&]() -> int {
        vector<vector<bool>> isUsed(n, vector<bool>(1001, false));
        // <targetNode, minSi>
        vector<vector<int>> dist(n, vector<int>(1001, 1e18));
        dist[0][s[0]] = 0;

        // <currentDist, currentNode>
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> hp;
        hp.push({0, 0, s[0]});
        while (!hp.empty()) {
            auto [curDist, curNode, minS] = hp.top();
            hp.pop();
            if (isUsed[curNode][minS]) {
                continue;
            }
            isUsed[curNode][minS] = true;

            for (auto &[nextNode, weight] : g[curNode]) {
                int nextS = min(minS, s[nextNode]);
                if (dist[nextNode][nextS] >= curDist + weight * minS) {
                    dist[nextNode][nextS] = curDist + weight * minS;
                    hp.push({dist[nextNode][nextS], nextNode, nextS});
                }
            }
        }
        return *min_element(dist[n - 1].begin(), dist[n - 1].end());
    };

    cout << dijkstra() << endl;
}