首页 > 其他分享 >P4568 [JLOI2011] 飞行路线

P4568 [JLOI2011] 飞行路线

时间:2024-04-12 16:33:05浏览次数:24  
标签:ch JLOI2011 int P4568 路线 edges define se dis

分层图的板子题

代码

#include <bits/stdc++.h>
#define R(x) x=read()
#define fi first
#define se second
using namespace std;

typedef pair<int,int> PII;
const int N = 1e4, M = 5e5;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

struct EdgeElement{
    int toP, val, ne;
}edges[M*11+5];

int h[N*11+5];
int n, m, k, s, t;
int idx;

inline void add(int a, int b, int c)
{
    edges[++idx].toP = b;
    edges[idx].ne = h[a];
    edges[idx].val = c;
    h[a] = idx;
}

inline void addDouble(int a, int b, int c)
{
    add(a, b, c);
    add(b, a, c);
}

bool vis[N*11 + 5];
int dis[N*11 + 5];

int DJ()
{
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    Q.push(make_pair(0, s));
    while(Q.size())
    {
        PII t = Q.top();
        Q.pop();
        if(vis[t.se])
            continue;
        for(int i = h[t.se]; i; i = edges[i].ne)
        {
            int j = edges[i].toP;
            if(dis[j] > dis[t.se] + edges[i].val)
            {
                dis[j] = dis[t.se] + edges[i].val;
                Q.push(make_pair(dis[j], j));
            }
        }
        vis[t.se] = 1;
    }
    return dis[t + n*k];
}

int main()
{
    // spots: 0~n-1
    R(n);R(m);R(k);
    R(s);R(t);
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        R(a);R(b);R(c);
        addDouble(a, b, c);
        for(int j = 1; j <= k; j++)
        {
            addDouble(a + j * n, b + j * n, c);
            add(a + (j - 1) * n, b + j * n, 0);
            add(b + (j - 1) * n, a + j * n, 0);
        }
    }
    // attention!
    // additional operations about T
    for(int i = 1; i <= k; i++)
        add(t + (i-1)*n, t + i*n, 0);
    printf("%d\n", DJ());
    return 0;
}

细节

1.插入不同层之间的节点时,只能插入单向边,不能插双向边,以样例为例:

 如果在不同层之间插入的是双向边,那就可以从起点走免费点到下一层,然后又走免费边回来……

最后零成本到达终点。

2.边数M的确定

起初我是这样算M的:

题目中给的m上限是5e4,先乘以二,然后又因为要加上十层图,再乘以11.

for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        R(a);R(b);R(c);
        addDouble(a, b, c);
        for(int j = 1; j <= k; j++)
        {
            addDouble(a + j * n, b + j * n, c);
            add(a + (j - 1) * n, b + j * n, 0);
            add(b + (j - 1) * n, a + j * n, 0);
        }
    }

我们可以看到,这里一次加了五条边,所以要再乘以5

3.终点的确定

for(int i = 1; i <= k; i++)
        add(t + (i-1)*n, t + i*n, 0);

因为我们这里把每一层的终点都连在一起了,所以可以直接把T+n*k作为终点;

如果没有进行这个操作的话,那就需要遍历每一层,dis[T+n*i]取min。

标签:ch,JLOI2011,int,P4568,路线,edges,define,se,dis
From: https://www.cnblogs.com/smartljy/p/18131603

相关文章

  • 2024最新网络安全学习路线+自学笔记(超详细)
    01什么是网络安全网络安全可以基于攻击和防御视角来分类,我们经常听到的“红队”、“渗透测试”等就是研究攻击技术,而“蓝队”、“安全运营”、“安全运维”则研究防御技术。无论网络、Web、移动、桌面、云等哪个领域,都有攻与防两面性,例如Web安全技术,既有Web渗透,也有W......
  • Java的学习路线(非常完整)
    Java是一种跨平台的、面向对象的高级编程语言,主要用来进行网站后台开发,也就是服务器端开发,或者动态网站开发。Java是全球最受欢迎的编程语言之一,在世界编程语言排行榜TIOBE中,Java一直霸占着前三名,有好多年甚至都是第一名。JetBrains每年都会发布一个开发者生态系统调查报......
  • NLP学习路线指南总结
    当然可以,以下是一份较为详细的NLP学习路线指南,帮助你逐步掌握自然语言处理的核心技术和应用。一、基础知识与技能语言学基础:语言学基本概念:语音、语法、语义等。语言的层次与分类:语音学、音系学、句法学、语义学等。编程基础:掌握Python编程语言基础,包括变量、数据类......
  • 别再抱怨学鸿蒙没方向了! 这鸿蒙全栈(南北双向)开发学习路线收藏好!
    在互联网技术不断发展的现在,鸿蒙操作系统的出现标志着是能技术领域的一次重大突破,鸿蒙作为华为推出的一代操作系统,鸿蒙不仅达代表了自主创新的力量,还因为独特的分布式架构和全场景适配能力而备受关注。随着鸿蒙生态的不断完善、壮大,学习鸿蒙开发技术不仅对IT专业人士来说是......
  • MySQL学习路线一条龙
    引言在当前的IT行业,无论是校园招聘还是社会招聘,MySQL的重要性不言而喻。面试过程中,MySQL相关的问题经常出现,这不仅因为它是最流行的关系型数据库之一,而且在日常的软件开发中,MySQL的应用广泛,尤其是对于Java后端开发者来说,熟练掌握MySQL已成为他们技术能力评估的重要指标。因此,My......
  • 抢先看!界面控件DevExpress WPF 2024产品路线图预览(二)
    DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。本文将介绍2024年DevExpressWPF第一个主要更新(v2......
  • Go+云原生高级开发工程师进阶路线及资料推荐
    云原生这几年非常火,很多同学都在学习云原生相关技术,我也在如何进阶为Go+云原生高级开发工程师?中,详细介绍了如何学习,以使自己快速进阶为Go+云原生高级开发。这里我再快速总结下学习路线,并提供路线中涉及到的学习资料供你下载。学习路线本着只看优秀课程、不重复学习、学习......
  • golang学习路线
    golang学习路线学习Golang的路线可以分为以下几个阶段:基础语法:了解Golang的基本语法结构,包括变量声明、控制流、函数、指针等。数据类型:熟悉Golang的基本数据类型,如整型、浮点型、字符串、数组、切片、Map等。并发编程:学习Golang的并发编程特性,包括goroutines、channels和互斥......
  • 零基础自学网络安全的三个必经阶段(含学习路线图)
    一、为什么选择网络安全?这几年随着我国《国家网络空间安全战略》《网络安全法》《网络安全等级保护2.0》等一系列政策/法规/标准的持续落地,网络安全行业地位、薪资随之水涨船高。未来3-5年,是安全行业的黄金发展期,提前踏入行业,能享受行业发展红利。二、为什么说网络安全行......
  • 抢先看!界面控件DevExpress WPF 2024产品路线图预览(一)
    DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。本文将介绍2024年DevExpressWPF第一个主要更新(v2......