forked from Amisha-here/Data-Structures
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.cpp
39 lines (36 loc) · 1023 Bytes
/
dijkstra.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define heap priority_queue
#define vpii vector<pii>
void addEdge(int v, int w, int d, vpii vec[]) {
vec[v].push_back(make_pair(d, w));
vec[w].push_back(make_pair(d, v));
}
void dij(int s, vpii graph[], int v) {
bool visited[v];
int dist[v];
heap < pii, vpii, greater<pii > > q;
for (int i = 0; i < v; i ++){
visited[i] = false;
dist[i] = - 1;
}
pii u;
u.first = 0;
u.second = s;
q.push(u);
int vertice;
while(!q.empty()) {
u = q.top();
vertice = u.second;
q.pop();
if (dist[vertice] == -1) {
dist[vertice] = u.first;
for (int i = 0; i < graph[vertice].size(); i ++) {
if (dist[graph[vertice][i].second] == - 1) {
q.push(make_pair(graph[vertice][i].first + dist[vertice], graph[vertice][i].second));
}
}
}
}
}