#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语言代码)浏览:1044 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:626 |
淘淘的名单 (C语言代码)浏览:1164 |
简单的a+b (C语言代码)浏览:557 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:940 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:862 |
字符串比较 (C语言代码)浏览:767 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:723 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:711 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2239 |