#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语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1057 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:506 |
十->二进制转换 (C语言代码)浏览:1327 |
回文数(一) (C语言代码)浏览:809 |
数组输出 (C语言代码)--此题的题目描述有问题浏览:1839 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:756 |
蚂蚁感冒 (C语言代码)浏览:814 |
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:725 |
简单的事情 (C语言代码)浏览:678 |
整除的尾数 (C语言代码)浏览:849 |