首页 > 其他分享 >[luoguP2901] Cow Jogging G

[luoguP2901] Cow Jogging G

时间:2024-11-08 22:19:05浏览次数:1  
标签:luoguP2901 cnt idx Cow int Jogging heap include Ginv

题意

给出一个 \(n\) 个点 \(m\) 条边的正权有向图,求从点 \(n\) 到点 \(1\) 的前 \(k\) 短路的距离分别是多少。

sol

\(k\) 短路问题往往使用 A* 算法(时间复杂度 \(O(nk\log n)\))或可持久化可并堆优化最短路树(时间复杂度 \(O((n+m) \log m + k \log k)\)),由于本题数据范围较小,可以使用更好写的 A* 算法。

A* 算法

A* 算法是启发式搜索的一种,其核心是估价函数 \(f(x)=g(x) + h(x)\),其中,\(g(x)\) 是当前到达状态 \(x\) 的最小代价,\(h(x)\) 是状态 \(x\) 到达目标状态的估计最小代价(该值必须不大于实际代价,且越大越好)。每次选择 \(f(x)\) 最小的未选择的状态,直到到达目标状态

\(k\) 短路

对于本题,我们计 \(h(x) = dist(x,1)\),这样可以保证一定不大于第 \(k\) 短路中这一段的距离。然后执行 A* 算法,当点 \(1\) 被遍历 \(k\) 次后,返回即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

#define x first 
#define y second 

using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;

const int N = 1005, M = 10005;

struct Graph{
    int h[N], e[M], w[M], ne[M], idx;

    Graph(){
        memset(h, -1, sizeof h);
    }

    void add(int a, int b, int c){
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }
} G, Ginv;

int n, m, k;
int h[N];
bool st[N];
int cnt[N];

void dijkstra(){
    memset(h, 0x3f, sizeof h);
    h[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (!heap.empty()){
        PII t = heap.top();
        heap.pop();
        if (st[t.y]) continue;
        st[t.y] = true;

        for (int i = Ginv.h[t.y]; ~i; i = Ginv.ne[i]){
            int j = Ginv.e[i];
            if (h[j] > h[t.y] + Ginv.w[i]) {
                h[j] = h[t.y] + Ginv.w[i];
                heap.push({h[j], j});
            }
        }
    }
}

void A_star(){
    priority_queue<PIP, vector<PIP>, greater<PIP>> heap;
    heap.push({h[n], {0, n}});
    while (!heap.empty()){
        PIP t = heap.top();
        heap.pop();
        cnt[t.y.y] ++ ;
        if (t.y.y == 1) {
            printf("%d\n", t.x);
            if (cnt[t.y.y] == k) return ;
        }

        for (int i = G.h[t.y.y]; ~i; i = G.ne[i]) {
            int j = G.e[i];
            if (cnt[j] > k) continue;
            heap.push({t.y.x + G.w[i] + h[j], {t.y.x + G.w[i], j}});
        }
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);

    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G.add(a, b, c), Ginv.add(b, a, c);
    }

    dijkstra();

    A_star();

    for (int i = cnt[1]; i < k; i ++ ) puts("-1");

    return 0;
}

标签:luoguP2901,cnt,idx,Cow,int,Jogging,heap,include,Ginv
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguP2901

相关文章

  • 封装技术 | CoWoS 封装工艺
    注:几篇关于CoWoS封装的合辑,有内容重叠,未整理。一文读懂先进封装CoWoS原创大K向前冲科技词话2024年06月05日08:31广东CoWoS,全称ChiponWaferonSubstrate,翻译过来就是“芯片在晶圆上,在基板上”。这个定义听起来有些拗口,但简单来说,它是一种先进的封装......
  • 题解:P3012 [USACO11FEB] Cowlphabet G
    [USACO11FEB]CowlphabetG题意有\(P\)种拼接方式,问由\(U\)个大写字母和\(L\)个小写字母合法组合的方案数。输出方案数对\(97654321\)取模的值。思路动态规划,还没有人写逆推方法,刚好我做的逆推。设\(f[i][j][z]\)表示一共有\(i\)个字母,其中\(j\)个为小写字母,......
  • P2952 [USACO09OPEN] Cow Line S
    [USACO09OPEN]CowLineS题面翻译FarmerJohn(以下简称FJ)的NNN头奶牛(用1…......
  • 洛谷 P2886 [USACO07NOV] Cow Relays G 做题记录
    设矩阵\(M^1=\begin{bmatrix}dis_{1,1}&\dots&dis_{1,n}\\\vdots&\ddots&\vdots\\dis_{1,n}&\cdots&dis_{n,n}\end{bmatrix}\),其中\(dis_{i,j}\)表示\(i\)是否能在\(1\)步内走到\(j\)。让我们回忆一下矩阵乘法,\(c_{i,j......
  • 清除openstack导出的qcow2格式的Windows16镜像的管理员密码
    由于公司使用的openstack版本太老,无法使用cloudbase-init传递元数据修改win16镜像的管理员密码,所以琢磨其它办法,搞了一个星期。原理:使用kpartx挂载镜像,然后使用chntpw清空密码,并修改cloudbase-init配置文件里的重置密码选项。准备环境系统:centos7.5磁盘80G(转换win16镜像由qcow......
  • [USACO23FEB] Hungry Cow P 题解
    T7[USACO23FEB]HungryCowP这题就比较正常了,蓝紫之间的水平。我们发现Bessie能活\(10^{14}\)天(,导致我们不好直接按照值域来维护。发现给某一天送干草,影响到的是后面很多天,这是个区间问题。所以考虑动态开点线段树。线段树的每个节点维护\(\mathit{ans},\mathit{cnt},\ma......
  • 题解:P9954 [USACO20OPEN] Cowntact Tracing B
    考虑暴力。枚举让每头牛都当一次“零号病人”和\(K\)的所有组合,模拟感染的过程,检查得出的病人是否和给出的一样即可。代码:#include<bits/stdc++.h>usingnamespacestd;boolinfectedd[101];intN,cowx[251],cowy[251];boolcheck(intpatient_zero,intK){ boolinfect......
  • 题解:P9939 [USACO21OPEN] Acowdemia III B
    考虑贪心。遍历每只奶牛:如果它最多与一头奶牛相邻,那么什么都不会发生。如果它与两头以上的奶牛相邻,那么它与两侧的两头奶牛相邻。将答案递增\(1\)。否则,如果正好有两头相邻的奶牛,我们就把它们配对。也就是说,将这对奶牛插入一组。代码:#include<bits/stdc++.h>usingname......
  • 题解:P1701 [USACO19OPEN] Cow Evolution B
    这题的关键就在于能否将问题转化成集合之间是否有交集。首先,考虑一个我们无法形成进化树的例子,例如这样:31fly1man2flyman如果我们想根据这个输入构建一棵树,我们需要在根上分割A或B,但剩下的两个子树都需要有一条边来添加另一个特征。显然输出为"No"。如果我们输入......
  • P10280 Cowreography G
    P10280CowreographyG贪心本题的证明中涵盖了多种证明方法:分类讨论,交换两个,整体策略,堪称贪心证明之典范符号约定令\(s_x\)表示最初字符串的不同\(1\)位置,\(t_x\)表示最终字符串的不同\(1\)位置Theorem1:交换\(a_i,a_j(i>j,a_i\nea_j)\)的最优步数为\(\lceil\fr......