1420：Dijkastra(II)
时间限制: 1000 ms 内存限制: 131072 KB
【题目描述】
给定一个无向连通图，求从1到n的最短路。
【输入】
第一行两个整数n,m,代表点数和边数；
接下来m行，每行三个整数s,t,d,代表从s到t有一条长度为d的无向边。
【输出】
输出一个整数表示最短距离。
【输入样例】
2 3
1 2 1
1 2 3
2 2 0
【输出样例】
1
【提示】
【数据规模及约定】
N≤200000,M≤400000,1≤S,T≤N,0≤D≤10^9
1. //示例代码 Dijkstrw 结构体优先级队列优化 2. #include <bits/stdc++.h> 3. using namespace std; 4. struct node{ 5. int num; 6. long long dist; 7. bool operator >(node y) const{ 8. return dist>y.dist; 9. } 10. }; 11. struct edge{ 12. int to,len; 13. }; 14. priority_queue<node,vector<node>,greater<node> > q; //优先队列，更快速 15. vector<edge> w[200050]; 16. long long dis[200050]; 17. int n,m,s,t,d; 18. bool vis[200050]; 19. int main() 20. { 21. cin>>n>>m; 22. for(int i=1; i<=m; i++){ 23. cin>>s>>t>>d;//输入 24. if(s==t) continue;//去除自环 25. w[s].push_back((edge){t,d}); 26. w[t].push_back((edge){s,d}); //推入邻接表 27. } 28. memset(dis,0x3f,sizeof(dis)); 29. dis[1]=0; 30. vis[1]=1; 31. q.push((node){1,0}); //初始化 32. while(!q.empty()){ 33. int k=q.top().num; 34. q.pop();//取值弹出 35. vis[k]=1;//访问过 36. for(int i=0;i<w[k].size();i++){ //算一遍 37. int p1=w[k][i].to,p2=w[k][i].len;//取出 38. if(!vis[p1]&&dis[k]+p2<dis[p1]){ 39. dis[p1]=dis[k]+p2;//更新 40. q.push((node){p1,dis[p1]}); //推入 41. } 42. } 43. } 44. cout<<dis[n]; 45. return 0; 46. }
