首页 > 编程语言 >2024“钉耙编程”中国大学生算法设计超级联赛(3)1008比特跳跃

2024“钉耙编程”中国大学生算法设计超级联赛(3)1008比特跳跃

时间:2024-07-30 20:20:34浏览次数:15  
标签:钉耙 cnt 比特 int 短路 2024 maxn 1008 跳跃

题目大意 :给出n个城市m条联通两个城市的无向边,从\(u_i\)到\(v_i\)需要耗费\(t_i\)的时间,你也可以选择进行一次比特跳跃,耗费k*(u|v)的时间
思路 :不难发现,比特跳跃最多跳跃一次。

证明:假设使用两次比特跳跃,a->b,c->d,那么权值为 k(a|b+c|d) ,不如直接从a->d,权值为 k(a|d),因为a|b+c|d >= min(a,b)+min(c,d)>=a+d>=a|d

所以1号点到每个点的最短路径上肯定最多只有一个比特跳跃的边
对于一个点,如果他想要从某个点比特跳跃跳到当前点,一定是从他的子集跳过来 不然答案肯定比从1号点跳过来更劣

由于刚开始的图可能不一定是连通图 所以我们要先让1号点连接其他点将图变成连通图。然后跑一遍最短路。
这个时候,已经初步得到了1号点跟其他点的最短路径

但是不一定是最优的
我们还需要将当前点的最短路跟从他子集中的最短路比特跳跃过来的值进行比较。
处理1->(走)y+y->(跳)x \(\leqslant\) 1->(初步最短路)x的情况;
在上述基础上再跑一次最短路就是最优答案

#include<bits/stdc++.h>  
#define int long long  
using namespace std;  
const int mod=998244353;  
const int maxn=5e6+10;  
int n,m,s,cnt=0;  
const int inf=1e18;  
int dis[maxn],h[maxn],to[maxn],val[maxn],nxt[maxn],vis[maxn],mind[maxn];  
struct node{  
    int v,w;  
    friend bool operator <(node a,node b){  
        return a.w>b.w;  
    }  
};  
priority_queue<node>q;  
void add(int a,int b,int c){  
    to[++cnt]=b;  
    val[cnt]=c;  
    nxt[cnt]=h[a];  
    h[a]=cnt;  
}  
void dijkstra(){  
    for(int i=0;i<=n;i++)dis[i]=inf;  
    dis[s]=0;  
    node tmp;  
    tmp.v=s;tmp.w=0;q.push(tmp);  
    while(!q.empty()){  
        int u=q.top().v;q.pop();  
        if(vis[u])continue;vis[u]=1;  
        for(int i=h[u];i;i=nxt[i]){  
            if(dis[to[i]]>dis[u]+val[i]){  
                dis[to[i]]=dis[u]+val[i];  
                tmp.w=dis[to[i]];  
                tmp.v=to[i];  
                q.push(tmp);  
            }  
        }  
    }  
}  
void solve(){  
    int k;  
    cnt=0;  
    cin>>n>>m>>k;  
    s=1;  
    memset(h,0,sizeof(h));  
    for(int i=0;i<=n;i++)vis[i]=0;  
    for(int i=1,u,v,w;i<=m;i++){  
        cin>>u>>v>>w;  
        add(u,v,w);  
        add(v,u,w);  
    }  
    for(int i=2;i<=n;i++){  
        add(1,i,(i|1)*k);  
        add(i,1,(i|1)*k);  
    }  
    dijkstra();  
    for (int i = 0; i <= n; i++) mind[i] = dis[i] , vis[i] = 0;  
    for (int i = 2; i <= n; i++){  
        for (int j = 0; (1<<j) <= n; j++) if ((i>>j)&1){  
                mind[i] = min(mind[i],mind[i^(1<<j)]);  
            }  
        dis[i] = min(dis[i],mind[i]+k*1ll*i);  
    }  
    dijkstra();  
    for(int i=2;i<=n;i++){  
        cout<<dis[i]<<' ';  
    }  
}  
signed main(){  
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);  
    int _=1;  
    cin>>_;  
    while(_--)solve();  
}

标签:钉耙,cnt,比特,int,短路,2024,maxn,1008,跳跃
From: https://www.cnblogs.com/yoez123/p/18333272

相关文章

  • 2024牛客暑期多校训练营5
    Preface坐牢,爽!前期经典屡次被签到腐乳导致罚时爆炸,写完四题后发现排名已经冲刺200+了,再一看后面的题都过的很少跟着榜看了一些题后感觉都不太可做,祁神和徐神一直在讨论J但我一点不想写大分类讨论Counting遂开摆摆到大概三点半的时候发现G题过的队越来越多了,看了眼题意......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(3) 1005 数论
    题意:分析:远看数论题,实则是道数据结构。记\(f_{i}\)表示\(r_{k}=i\)的方案数,\(g_{i}\)表示\(l_{1}=i\)的方案数,那么运用简单容斥,可得:\[ans_{x}=(\sum_{i=1}^{n}f_{i})-((\sum_{i=1}^{x-1}f_{i})+1)\times((\sum_{i=x+1}^{n}g_{i})+1)+1\]先考虑如何计算\(f_{i......
  • c语言笔记(2024.7.24)第三天
    常量与变量概念:·表面:程序运行过程中取值可以改变的数据·实际:变量其实代表了一块内存区域/单元/空间。变量名可视为该区域的标识。整个变量分为三部分:·变量名:这个只是变量的一个标识,我们借助变量名来存取数据。·变量空间/存储单元:这个就是内存中分配的一块用来存放......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(1)1012并
    题目大意:给出n个矩形,求被k个矩形覆盖的面积的并集的期望,输出k为1-n的所一答案思路:由于是求期望所以是求出所有情况的和再除以可能的情况,每一种情况中的面积都由--同时被1个矩形覆盖,同时被两个矩形覆盖······同时被k个矩形覆盖组成,而且不难得出当k一定时,取被m个矩形覆盖的......
  • 【调试笔记-20240730-Linux-OpenWrt 23.05 安装 Docker 配置 bitnami/Wordpress-with-
    调试笔记-系列文章目录调试笔记-20240730-Linux-OpenWrt23.05安装Docker配置bitnami/Wordpress-with-NGINX实现微信用户在线注册登录文章目录调试笔记-系列文章目录调试笔记-20240730-Linux-OpenWrt23.05安装Docker配置bitnami/Wordpress-with-NGINX实现......
  • 2024-7-30 信友队模考总结
    开考这次的题目看着比较简单,第一题一眼前缀和,第二题是双指针,三四题不很一眼,感觉可以冲300pts。果然T1直接秒掉,J组难度。开写第二题感觉是双指针,而且也很有单调性,但是怎么实现并没有一下想出来,写了大概10min过了样例和自测,但是观摩的时候发现假了,我写的是伪双指针,\(\math......
  • 企业常用源代码加密软件,2024五款源代码加密软件推荐
    在现代企业中,源代码是核心资产之一,其安全性对企业的竞争力和创新能力至关重要。为了防止代码泄露和未经授权的访问,许多企业选择使用源代码加密软件。以下是2024年五款值得推荐的源代码加密软件,为企业提供可靠的安全保障。1.安秉源代码加密软件安秉源代码加密软件是一款专为......
  • 2024夏令营CTF部分wp
    misc前面几题基本来源于这篇文章>https://blog.csdn.net/qq_45894840/article/details/128346180?spm=1001.2014.3001.5502算是misc的入门级题目,就不多说了1.easy_stego_1是盲水印分离的题目首先拿到题目附件>http://nnd.edaker.com:8999/directlink/2/misc_easy_stego_1.p......
  • 2024 年求职不易,有没有什么效率高的求职方法?
    对于很多打工人来说,今年过得并不容易,不管是打工还是求职,都感觉艰难许多。市场竞争力变大,让许多打工人都感受到了浓浓的“求职焦虑”。对于应届生而言,今年更是具有挑战性的一年,毕业人数量高达1179万人,又创历史新高,毕业生的增多,就意味着就业竞争压力更大…在这样的就业形势下,最......
  • 【往届会后三个半月内EI检索 | EI会议征稿 】第四届物联网与机器学习国际学术会议(IoTM
     第四届物联网与机器学习国际学术会议(IoTML2024)20244th InternationalConferenceonInternetofThingsandMachineLearning重要信息大会时间:2024年8月9-11日         大会地点:中国-南昌        大会官网:www.iotml.cn   会......