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

P4568 [JLOI2011] 飞行路线

时间:2024-09-14 16:23:52浏览次数:10  
标签:head JLOI2011 int P4568 cnt 路线 vis id dis

P4568 [JLOI2011] 飞行路线

考虑跑多层图,每层图连条边权为0的边,跑 dijkstra 即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e7+10;
int n,m,k,s,t;


int cnt;
int head[N];

struct ss{
	int to,w,next;
}a[N];

void add(int u,int v,int w){
	a[cnt].to=v;
	a[cnt].w=w;
	a[cnt].next=head[u];
	head[u]=cnt++;
}

struct no{
	int id,di;
	bool operator < (const no &g) const {
		return di>g.di;
	}
};

int dis[N];
int vis[N];

priority_queue<no> q;

void dijkstra(int x){
	memset(dis,0x3f,sizeof dis);
	
	dis[x]=0;
	q.push({x,0});
	
	while(!q.empty()){
		no u=q.top();
		q.pop();
		if(vis[u.id]){
			continue;
		}
		vis[u.id]=1;
		for(int i=head[u.id];~i;i=a[i].next){
			int y=a[i].to;
			if(vis[y]){
				continue;
			}
			if(dis[y]>dis[u.id]+a[i].w){
				dis[y]=dis[u.id]+a[i].w;
				q.push({y,dis[y]});
			}
		}		
	}
} 

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>s>>t;
    
    memset(head,-1,sizeof head);
    
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	add(u,v,w);
		add(v,u,w);
		
		for(int j=1;j<=k;j++){
			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0);
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);
		}    	
	}
	
	for(int i=1;i<=k;i++){//题解上写的,防止负权边
		add(t+(i-1)*n,t+i*n,0); 
	}	
	
	dijkstra(s);
	
	cout<<dis[t+k*n];
	
    return 0;
}

标签:head,JLOI2011,int,P4568,cnt,路线,vis,id,dis
From: https://www.cnblogs.com/sadlin/p/18414273

相关文章

  • 大语言模型(LLM)入门学习路线图
    Github项目上有一个大语言模型学习路线笔记,它全面涵盖了大语言模型的所需的基础知识学习,LLM前沿算法和架构,以及如何将大语言模型进行工程化实践。这份资料是初学者或有一定基础的开发/算法人员入门活深入大型语言模型学习的优秀参考。这份资料重点介绍了我们应该掌握哪些核......
  • 网络计划技术——关键路线法精解
    网络计划技术最早由美国杜邦公司于1957年开发的“关键路径法(CPM)”和美国海军在1958年发明的“计划评审技术(PERT)”推动。网络计划技术(NetworkPlanningTechniques)是一种用于项目管理和调度的科学方法,其核心思想是通过构建网络图来描述项目中各个任务之间的逻辑关系,进而分析和优化......
  • 网络安全学习路线图(2024版详解)
      近期,大家在网上对于网络安全讨论比较多,想要学习的人也不少,但是需要学习哪些内容,按照什么顺序去学习呢?其实我们已经出国多版本的网络安全学习路线图,一直以来效果也比较不错,本次我们针对市场需求,整理了一套系统的网络安全学习路线图,供大家学习参考。希望大家按照路线图进行......
  • 2024网络安全学习路线 非常详细 推荐学习
      关键词:网络安全入门、渗透测试学习、零基础学安全、网络安全学习路线首先咱们聊聊,学习网络安全方向通常会有哪些问题1、打基础时间太长学基础花费很长时间,光语言都有几门,有些人会倒在学习linux系统及命令的路上,更多的人会倒在学习语言上;2、知识点掌握程度不清楚对......
  • 2024网络安全学习路线 非常详细 推荐学习
      关键词:网络安全入门、渗透测试学习、零基础学安全、网络安全学习路线首先咱们聊聊,学习网络安全方向通常会有哪些问题1、打基础时间太长学基础花费很长时间,光语言都有几门,有些人会倒在学习linux系统及命令的路上,更多的人会倒在学习语言上;2、知识点掌握程度不清楚对......
  • 自学网络安全的三个必经阶段(含路线图)
           一、为什么选择网络安全?这几年随着我国《国家网络空间安全战略》《网络安全法》《网络安全等级保护2.0》等一系列政策/法规/标准的持续落地,网络安全行业地位、薪资随之水涨船高。未来3-5年,是安全行业的黄金发展期,提前踏入行业,能享受行业发展红利。二、为什么......
  • 自学网络安全的三个必经阶段(含路线图)
           一、为什么选择网络安全?这几年随着我国《国家网络空间安全战略》《网络安全法》《网络安全等级保护2.0》等一系列政策/法规/标准的持续落地,网络安全行业地位、薪资随之水涨船高。未来3-5年,是安全行业的黄金发展期,提前踏入行业,能享受行业发展红利。二、为什么......
  • 2024网络安全学习路线 非常详细 推荐学习_网络安全教程谁的好
    关键词:网络安全入门、渗透测试学习、零基础学安全、网络安全学习路线首先咱们聊聊,学习网络安全方向通常会有哪些问题1、打基础时间太长学基础花费很长时间,光语言都有几门,有些人会倒在学习linux系统及命令的路上,更多的人会倒在学习语言上;2、知识点掌握程度不清楚对于......
  • 黑客零基础入门教程,从入门到精通学习路线&规划,看完这篇就够了。
    很多人上来就说想学习黑客,但是连方向都没搞清楚就开始学习,最终也只是会无疾而终!黑客是一个大的概念,里面包含了许多方向,不同的方向需要学习的内容也不一样。想要成为黑客,却苦于没有方向,不知道从何学起,下面这篇黑客入门教程可以帮你实现自己的黑客梦想,如果想学,可以继续看下去......
  • 机器视觉的学习路线
    学习计算机视觉可以分为多个阶段,每个阶段都有其核心主题和推荐的学习资源。以下是一个系统的学习路线:1.基础知识1.1数学基础线性代数:矩阵运算、特征值与特征向量概率与统计:概率分布、贝叶斯定理微积分:导数、偏导数、链式法则1.2编程基础Python:学习基本语......