#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e5+10; int dis[N],e[N],ne[N],h[N],idx,w[N]; bool st[N];//判断是否在队列里面 int n,m; void add(int a,int b,int x) { e[idx]=b,w[idx]=x,ne[idx]=h[a],h[a]=idx++; } int spfa() { memset(dis,0x3f,sizeof dis); //神似堆优化版的dijkstra queue<int> q; dis[1]=0; q.push(1); st[1]=true; while(q.size()) { auto t=q.front(); q.pop(); st[t]=false; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } return dis[n]; } int main(void) { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } cout<<spfa(); return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:596 |
C语言训练-尼科彻斯定理 (C语言代码)浏览:504 |
【蟠桃记】 (C语言代码)浏览:685 |
a+b浏览:445 |
矩形面积交 (C++代码)浏览:1198 |
陈教主的三角形 (C语言代码)浏览:1182 |
良心推荐——>题解1049:C语言程序设计教程(第三版)课后习题11.1 (C语言描述——简单明了,时间复杂度低)浏览:1308 |
上车人数 (C语言代码)浏览:748 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:563 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:676 |