(模板)poj2387(dijkstra+优先队列优化模板题)
2024-09-05 06:40:06
题目链接:https://vjudge.net/problem/POJ-2387
题意:给n个点(<=1000),m条边(<=2000),求结点n到结点1的最短路。
思路:dijkstra优先队列,复杂度O(nlogn)。
AC代码:
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=1e3+;
const int inf=0x3f3f3f3f;
int m,n,cnt,head[maxn],dis[maxn],vis[maxn];
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > pq; struct node{
int v,w,nex;
}edge[maxn<<]; void adde(int u,int v,int w){
edge[++cnt].v=v;
edge[cnt].w=w;
edge[cnt].nex=head[u];
head[u]=cnt;
} void dijkstra(){
pq.push(make_pair(,n));
for(int i=;i<=n;++i)
dis[i]=inf;
dis[n]=;
int num=;
while(!pq.empty()&&num<=n){
int d=pq.top().first,u=pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u]=;
++num;
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v,w=edge[i].w;
if(!vis[v]&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
pq.push(make_pair(dis[v],v));
}
}
}
} int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adde(u,v,w);
adde(v,u,w);
}
dijkstra();
printf("%d\n",dis[]);
return ;
}
最新文章
- iOS开发之Masonry框架源码深度解析
- XAF学习笔记1
- Linux Ubuntu12.04下安装OpenCv2.4.10
- yii2中事务不能回滚的解决
- 【CSS】css网页背景图片设置
- C# (事件触发)回调函数,完美处理各类疑难杂症!
- stm32f107vc在IAR环境下,引用库函数的工程文件的配置方法
- cocos2d-x设计模式发掘之五:防御式编程模式
- [Q]图框识别问题
- RTL-SDR基础环境安装
- 关于IP网段间互访的问题—路由是根本(转)
- Eclipse插件的各种安装方法
- 【JDK1.8】JDK1.8集合源码阅读——TreeMap(一)
- Mysql双主互备+keeplived高可用架构(部分)
- bootstrap 失效的原因
- android Service oncreate 在UI线程 何时用service,何时用thread
- [开源项目-MyBean轻量级配置框架] MyBean的特性和MyBean的开始
- Window环境下搭建Vue.js开发环境
- c/c++--strlen()小问题
- 利用Java反射实现JavaBean对象相同属性复制并初始化目标对象为空的属性的BeanUtils
热门文章
- Guardian of Decency POJ - 2771 【二分匹配,最大独立集】
- 五十一.Openstack概述 部署安装环境 、 部署Openstack OpenStack操作基础
- web开发下载文件夹
- linux认识
- leetcode解题报告(3):Search in Rotated Sorted Array
- 关于scala
- Luogu5339 [TJOI2019]唱、跳、rap和篮球 【生成函数,NTT】
- 前端逼死强迫症系列之javascript
- Codeforces 1239D. Catowice City
- 使用setUncaughtExceptionHandler在线程外面捕获异常