首页 > 其他分享 >考前10模板

考前10模板

时间:2022-08-26 09:22:07浏览次数:75  
标签:10 head 考前 int tot vis 模板 dis

单源最短路-dijkstra+优先队列优化

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=5e5+10;
int n,m,s,bb=1;
int dis[N],vis[N];//vis为是否已成无法再次更新的点 
struct node{
	int x,y;
	bool operator > (const node & a) const //重载运算符 ,x小才算小的 
	{
		return x>a.x;
	}
};
priority_queue<node,vector<node>,greater<node> > q;//优先队列优化 
int tot=1,head[N],ver[M],edge[M],Next[M];//链式前向星存图 
void add(int x,int y,int z)
{
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push({dis[s],s});
	while(!q.empty())
	{
		int x=q.top().y;
		q.pop();
		if(vis[x])
			continue;
		vis[x]=1;
		for(int i=head[x];i;i=Next[i])
		{
			int y=ver[i];
			if(!vis[y]&&dis[y]>dis[x]+edge[i])
			{
				dis[y]=dis[x]+edge[i];
				q.push({dis[y],y});
			}	
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dijkstra();
	for(int i=1;i<=31;i++)
		bb*=2;
	bb-=1;
	for(int i=1;i<=n;i++)
	{
		if(dis[i]!=0x3f3f3f3f)
			printf("%d ",dis[i]);
		else
			printf("%d ",bb);
	}
 	return 0;
}

标签:10,head,考前,int,tot,vis,模板,dis
From: https://www.cnblogs.com/kezhuo/p/16626472.html

相关文章

  • 【Location Kit】定位服务设置时间间隔mLocationRequest.setInterval(15 * 1000)不起
    ​ 【问题描述】mLocationRequest.setInterval(5*1000);//设置5″  定位返回间隔10″mLocationRequest.setInterval(10*1000);//设置10″ 定位返回间隔10″......
  • CF1066C 题解
    前言题目传送门!更好的阅读体验?本题是简单的双端队列练手题。思路题意大致如下:执行双端队列push_front()操作。执行双端队列push_back()操作。查询\(\min\{m......
  • P8410 题解
    前言题目传送门!更好的阅读体验?本次比赛第二题,好像没有人抢题解,那我来一发。思路还是挺巧妙的。\(\texttt{10pts}\)思路深搜求解即可。最坏情况,时间复杂度\(O(n!......
  • day3:101-A1-Kali Linux安装
    KaliLinux安装物理机什么是Kali系统KaliLinux是Linux系统的其中一版本,Kali其中自带了600余种安全工具,主要用于渗透测试、安全研究、计算机取证、逆向工程等等。......
  • 洛谷-P3388 【模板】割点(割顶)
    【模板】割点(割顶)tarjan学了一下割点,发现就是找\(low[nex]\gedfn[now]\)的点,同时根的话要求有两个分支才能作为割点搜索的时候如果\(nex\)没有被访问过,则直接继续......
  • 题解 UVA10869 Brownie Points II
    题意平面上有若干点,\(\text{stan}\)通过一个点划了一条直线,\(\text{ollie}\)通过在这条直线上的点作了一条垂线,那么平面被分成\(4\)个象限,\(\text{stan}\)获得的分数......
  • 101. 对称二叉树
    101.对称二叉树给你一个二叉树的根节点root,检查它是否轴对称。 示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:输入:root=[1,2,2,null,3,null,3]输出:fa......
  • 蔚来杯2022牛客暑期多校训练营10 题解
    D.MiReDoSiLa?SoFa![NOI2016]优秀的拆分原题。枚举周期\(k\),并将位置为\(k\)的倍数的点设为关键点。枚举相邻两个点\(i,i+k\),并求出\(lcp(S[i...n],S[i+k......
  • 斯坦福CS107 编程范式07
    探索,使用栈的定义,定义一个通用类型的栈来存储一系列的字符串,并把它们以相反的顺序打印出来。 typedefstruct{void*elems;intelemSize;intloglength......
  • 2022“杭电杯”中国大学生算法设计超级联赛(10) 题解
    C.WavyTree发现修改次数和相邻两数的相对大小有关,所以可先求出差分数组。分两种情况考虑:①奇数位置为波峰②偶数位置为波峰。以情况①为例,若奇数位置差分后值小......