数据结构-Dijskra(迪杰斯特拉)最短路径算法

本文主要是介绍数据结构-Dijskra(迪杰斯特拉)最短路径算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：https://www.dotcpp.com/oj/problem1708.html

今天打算打一下午的最短路，刷上十道题最短路就算完结了，开刷

其实这道题挺迷的，这个题最大的坑点就是不能双向存图，我也不知道为什么不能存双边，但是存了双边就过不了，先不探究了，先刷题；

然后就是常规的djkstra了；

Talk is cheap. Show me the code.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int num=100;
 4 const int INF=0x3f3f3f3f;
 5 int n;
 6 int s;
 7 struct edge
 8 {
 9     int from;
10     int to;
11     int w;
12     edge(int a,int b,int c)
13     {
14         from=a;
15         to=b;
16         w=c;
17     }
18 };
19 vector<edge>e[num];
20 struct node
21 {
22     int id;
23     int d;
24     node(int b,int c)
25     {
26         id=b;
27         d=c;
28     }
29     bool operator<(const node &a)const
30     {
31         return d>a.d;
32     }
33 };
34 int dis[num];
35 void dijkstra()
36 {
37     bool done[num];
38     for(register int i=0;i<n;i++)
39     {
40         dis[i]=INF;
41         done[i]=false;
42     }
43     dis[s]=0;
44     priority_queue<node>q;
45     q.push(node(s,dis[s]));
46     while(!q.empty())
47     {
48         node u=q.top();
49         q.pop();
50         if(done[u.id])
51         continue;
52         done[u.id]=true;
53         for(register int i=0;i<e[u.id].size();i++)
54         {
55             edge y=e[u.id][i];
56             if(done[y.to])
57             continue;
58             if(dis[y.to]>y.w+u.d)
59             {
60                 dis[y.to]=y.w+u.d;
61                 q.push(node(y.to,dis[y.to]));
62             }
63         }
64     }
65 //    printf("%d ",dis[n]);
66 }
67 int main()
68 {
69     std::ios::sync_with_stdio(false);
70     cin.tie(0);
71     cout.tie(0);
72     cin>>n>>s;
73     for(register int i=0;i<n;i++)
74     {
75         for(register int j=0;j<n;j++)
76         {
77             int temp;
78             cin>>temp;
79             if(temp)
80             {
81                 e[i].push_back(edge(i,j,temp));
82                 //e[j].push_back(edge(j,i,temp));    //不要存双边
83             }
84         }
85     }
86      dijkstra();
87     for(register int i = 0; i < n; i++){
88         if(i!=s){//跳过那个起点
89             if(dis[i] == INF){
90                 printf("-1 ");
91             }else{
92                 printf("%d ", dis[i]);
93             }
94         }
95     }
96     return 0;
97 }

这篇关于数据结构-Dijskra(迪杰斯特拉)最短路径算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！