Algorithms/2. Dijktra algo.cpp at master · ugouhar/Algorithms · 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
87
88
89
90
91
// #include<bits/stdc++.h>
// #define ll long long int
// #define pll pair<ll,ll>
// #define vll vector<ll>
// #define pb push_back
// #define inf 1000000000000000000
// #define fastIO ios_base::sync_with_stdio(0);\
//                cin.tie(NULL);\
//                cout.tie(NULL)

// using namespace std;


// vector<pll> adj[10004];
// bool vis[10004];
// priority_queue<pll,vector<pll>,greater<pll>> pq;
// ll dist[10004];


// void relax(ll curr)
// {
// 	if(vis[curr])
// 			return;
// 	vis[curr]=true;

// 	for(auto i:adj[curr])
// 	{
// 		if(!vis[i.second])
// 		{
// 			if(dist[curr]+i.first < dist[i.second])
// 			{
// 				dist[i.second] = dist[curr]+i.first;
// 				pq.push({dist[i.second],i.second});
// 			}
// 		}
// 	}
// }


// void dijktra(ll n,ll s)
// {
// 	dist[s]=0;
// 	pq.push({0,s});

// 	while(!pq.empty())
// 	{
// 		ll curr=pq.top().second;
// 		pq.pop();
// 		relax(curr);
// 	}
// }


// int main()
// {
// 	fastIO;
// 	freopen("input.txt","r",stdin);


// 	ll n,m;	//n nodes, m edges
// 	cin>>n>>m;


// 	for(ll i=0 ; i<m ; i++)
// 	{
// 		ll u, v, cost;	//edge from u to v
// 		cin>>u>>v>>cost;
// 		adj[u].pb({cost,v});
// 	}


// 	for(ll i=0 ; i<=n ; i++)	//initializatoin 1
// 	{
// 		vis[i]=false;
// 		dist[i]=inf;
// 	}

// 	ll s;	//source vertex
// 	s=1;
// 	dijktra(n,s);

// 	for(ll i=2 ; i<=n ; i++)
// 	{
// 		cout<<dist[i]<<' ';
// 	}

// 	return 0;
// }