C-codes/dijkstra.cpp at master · ishanagarwal1606/C-codes · GitHub

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<queue>

using namespace std;

#define rep(i,m,n) for(ll i = m; i < n; i++)
#define pb push_back
#define mp(x,y) make_pair(x,y)
#define F first
#define S second
#define ll long long
#define N 100001
#define inf 1000000000000000001

class Dijkstra
{
	public:
		vector<pair<ll,ll> > adj[N];
		ll parent[N];
		ll key[N];
		bool inSS[N];

		void begin()
		{
			ll nodes,edges,x,y,w;
			cin>>nodes>>edges;
			rep(i,0,edges)
			{
				cin>>x>>y>>w;
				adj[x].pb(mp(y,w));
				adj[y].pb(mp(x,w));
			}

			rep(i,0,N)
			{
				parent[i]=-1;
				inSS[i]=false;
				key[i]=inf;
			}

			DijkstraAlgo();
			printShortestPath();
		}

		void DijkstraAlgo()
		{
			priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > Q;
			pair<ll,ll> x;
			ll source=0;
			key[source]=0;
			Q.push(mp(key[source],source));
			while(!Q.empty())
			{
				x=Q.top();
				Q.pop();
				inSS[x.S]=true;
				for(auto p:adj[x.S])
				{
					if(!inSS[p.F]&&(p.S+x.F)<key[p.F])
					{
						key[p.F]=p.S+x.F;
						Q.push(mp(key[p.F],p.F));
						parent[p.F]=x.S;
					}
				}
			}
		}

		void printShortestPath()
		{
			rep(i,0,N+1)
			{
				if(inSS[i])
				{
					cout<<"Node::"<<i<<"  Distance from source::"<<key[i]<<endl;
				}
			}
		}
};

int main()
{
	Dijkstra d;
	d.begin();
	return 0;
}