C++-POJ2159-Candies[spfa][栈优化][邻接表]
2024-10-08 10:06:14
#include <cstdio>
const int M=,N=;
struct edge{int v,w,next;}e[M];int head[N],cnt;
void add(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt;}
int d[N],vis[N],stack[M],top;
int spfa(int n){
for(int i=;i<=n;i++)vis[i]=,d[i]=;
top=,stack[++top]=,vis[]=,d[]=;
for(int u;top>=;){
u=stack[top--],vis[u]=;
for(int i=head[u],v,w;v=e[i].v,w=e[i].w,i;i=e[i].next)
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!vis[v])stack[++top]=v,vis[v]=;
}
}
return d[n];
}
int main(){
for(int n,m,u,v,w;scanf("%d%d",&n,&m)!=EOF;){
for(int i=;i<=n;i++)head[i]=;
while(m--)scanf("%d%d%d",&u,&v,&w),add(u,v,w);
printf("%d\n",spfa(n));
}
return ;
}
最新文章
- linux中redis安装
- 问题解决_(转载)VS2015无法启动 IIS Express Web解决办法
- val()方法
- python——生成器
- Object-C — KVO &; oc通知
- Python之路:线程池
- Ibatis教程
- 月薪20k以上的高级程序员需要学习哪些技术呢?
- AIX7.1环境打补丁缺少bash OPATCHAUTO-72049
- os.path官方文档(附翻译)
- 安装jdk+tomcat
- Confluence 6 其他 MBeans 和高 CPU 消耗线程
- 【官档整理】Visual Studio 2017 VS2017 中文离线安装包下载
- [05] Bean的作用域和生命周期
- Python中的join()函数的用法及列表推导式
- 【LeetCode每天一题】Combination Sum II(组合和II)
- Opencv-Python 图像透视变换cv2.warpPerspective
- MySQL之多表查询练习 与基本查询基础
- 基于udp协议的套接字,socketserver模块,多道技术,进程理论
- mac上查找nginx安装位置
热门文章
- opencv —— setMouseCallback 响应鼠标操作事件
- CF1311E Construct the Binary Tree
- linux cpp (接口与实现的分离)
- w13scan扫描器的使用
- 小Z的袜子(hose) HYSBZ - 2038 莫队+分块
- 剑指offer-面试题40-最小的k个数-最大堆
- P1055 ISBN号码(getline(cin,s); printf(";%s";,str); )
- XSS攻击解决办法 Spring mvc databinder
- Java 【instanceof使用】
- 第一个12PB的项目--2017年