#include
#include<bits/stdc++.h>
#include<unordered_map>
#include
#include
#include
#include
using namespace std;
template
class graph{
unordered_map<t,list<pair<t,int>>> m;
public:
void addedge(t u,t v, int dist,bool isbid=true)
{
m[u].push_back(make_pair(v,dist));
if(isbid==true)
{
m[v].push_back(make_pair(u,dist));
}
}
void dijsktra( t src)
{
unordered_map<t,int> dist;
//make a set to find a node with min distance
for(auto j: m)
{
dist[j.first]=INT_MAX;
}
dist[src]=0;
set<pair<int,t>>s;
s.insert(make_pair(0,src));
while(!s.empty())
{
auto p=*(s.begin());
t node=p.second;
int nodedist=p.first;
//s.erase(s.find(p));//
s.erase(s.begin());
for(auto childpair:m[node])
{ auto dest=childpair.first;
if(nodedist+childpair.second<dist[childpair.first])
{ //in set updatation is not possible so we will delete one and update or add new one//
auto f= s.find(make_pair(dist[dest],dest));
if(f!=s.end())
{
s.erase(f);
}
//insert the new pair
dist[dest]=nodedist+childpair.second;
s.insert(dist[dest],dest);
}
}
}
for(auto it:dist)
{
// cout<<"distance of"<<it.first<<"from"<<src<<"is"<<it.second<<endl;
}
}
};
int main() {
graph g;
g.addedge(1,2,1);
g.addedge(1,3,4);
g.addedge(2,3,1);
g.addedge(3,4,2);
g.addedge(1,4,7);
g.dijsktra(1);
}