#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=1e5+10; //数据较大时 int dis[N],h[N],e[N],w[N],ne[N],idx; //用邻接表存储 bool st[N]; int n,m,q; int hh,ww; typedef pair<int,int> PII; void add(int a,int b,int x) { e[idx]=b,w[idx]=x,ne[idx]=h[a],h[a]=idx++; } int find() { memset(dis,0x3f,sizeof dis); dis[1]=0; memset(st,0,sizeof st); //st必须初始化为0,否则if过不去 priority_queue<PII,vector<PII>,greater<PII> > heap; //优先队列+堆 heap.push({0,1}); //距离,节点 while(heap.size()) { PII t=heap.top(); heap.pop(); int dian=t.second,di=t.first; if(st[dian])continue; //如果该点已经是最短 就跳过 (存在多边情况是,链表存储可能又回到这个点) st[dian]=true; for(int i=h[dian];i!=-1;i=ne[i]) { //cout<<"hh"; int j=e[i]; //i只是下表,e存储下标中对应的点 if(dis[j]>di+w[i]) //更新 { dis[j]=di+w[i]; heap.push({dis[j],j}); } } } return dis[n]; } int main(void) { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int a,b,x; cin>>a>>b>>x; add(a,b,x); } cout<<find(); return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:663 |
C二级辅导-计负均正 (C语言代码)浏览:545 |
C语言程序设计教程(第三版)课后习题11.11 (C语言代码)浏览:795 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1126 |
C语言训练-排序问题<1> (C++代码)浏览:621 |
数列排序 (C语言代码)浏览:856 |
C语言训练-角谷猜想 (C语言代码)浏览:1755 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:553 |
简单的a+b (C语言代码)浏览:666 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:602 |