首页 > 其他分享 >G. Bicycles 分层图单源最短路

G. Bicycles 分层图单源最短路

时间:2023-12-30 19:45:30浏览次数:40  
标签:dist 短路 nextNode 单源 Bicycles vector nextS minS hp

题目链接
简单描述一下题意:
给定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;
}

标签:dist,短路,nextNode,单源,Bicycles,vector,nextS,minS,hp
From: https://www.cnblogs.com/whysopt/p/17936708

相关文章

  • G. Bicycles
    G.BicyclesAllofSlavic'sfriendsareplanningtotravelfromtheplacewheretheylivetoapartyusingtheirbikes.AndtheyallhaveabikeexceptSlavic.Thereare$n$citiesthroughwhichtheycantravel.Theyallliveinthecity$1$andwant......
  • Dijkstra实现单源最短路
    Dijkstra算法求单源最短路Dijkstra算法应用于求一个给定图的单个源点到其他各顶点的最短路。其中应用Dijkstra算法的图应满足如下条件图中没有负权边有向或者无向图都可以图中若有自环或者重边也可以(需要自己先筛选一下)Dijkstra算法的核心就是从源点开始对各个顶点进行......
  • 洛谷B3647 【模板】Floyd 题解 floyd算法 求 多源多汇最短路
    题目链接:https://www.luogu.com.cn/problem/B3647floyd算法:https://oi-wiki.org/graph/shortest-path/#floyd-算法示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=101;intn,m,f[maxn][maxn];intmain(){scanf("%d%d",&n......
  • P1339 [USACO09OCT] Heat Wave G 最短路入门题 Dijkstra/SPFA/Dijkstra+优先队列优化
    目录朴素的Dijkstra算法SPFA算法Dijkstra+优先队列优化题目链接:https://www.luogu.com.cn/problem/P1339题目大意:无向图有单源最短路。朴素的Dijkstra算法时间复杂度\(O(n^2)\)。#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2505;structEdge......
  • 最短路计数
    前置知识最短路的一个很好的性质:从\(s\)到\(t\)的最短路上的一个节点\(k\),都满足\(s\)到\(k\)的路径是关于\(s\)单源最短路的最短路证明:反证法,假设\(s\)到\(k\)的路径不为最短路,但\(s\tok\tot\)为到\(t\)的最短路,那么\(s\tok\tot\)的路径一定不会比\(s\)到\(k\)的最......
  • 7-5 单源最短路径
    7-5单源最短路径请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点,编号为0至n-1,以顶点0作为源点。输入格式:输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过1000。接下来e行表示每条边的信息,每行为3个非负整数a、b、c,其中a和b表示......
  • 图论——最短路
    https://csacademy.com/app/graph_editor/https://riverhamster.gitee.io/app/graph_editor/注:时间复杂度分析中,假设\(n\lem\len^2\)最短路本质上是一种DP阶段:点状态:拆点决策:边最优子结构:最短路的任何子路径都一定是最短路无后效性:正权图中一定可以找到一种无后......
  • 使用OCCT构建两个面之间的最短路径
    查找两个面之间的最短面路径查找面的邻面。std::vector<TopoDS_Face>OCCTUtility::adjacentFace(TopoDS_Faceconst&face,std::optional<TopoDS_Shape>shape,std::optional<TopTools_IndexedDataMapOfShapeListOfShape>edgeMapFace){std::vector<TopoD......
  • dijkstra最短路
    给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y的......
  • 12.11 迪杰斯特拉方法实现最短路径(c++)
     今天通过自主学习,,对数据结构中的迪杰斯特拉方法实现最短路径进行了深造,让我学会了很多新的东西。首先是问题描述:用迪杰斯特拉算法实现有向网的最短路径输入格式:第一行输入有向网的顶点和边数,第二行输入各顶点值,用空格间隔,第三行开始输入各条边的两个点的及边上的权值,用空......