#include
#include<bits/stdc++.h>
using namespace std;
class Graph{
map<string ,list<pair<string,int> > > l;
public:
void addedge(string x,string y,int dist)
{
l[x].push_back(make_pair(y,dist));
l[y].push_back(make_pair(x,dist));
}
void dikstra(string src)
{
map<string,int> dist;
for(auto z:l)
dist[z.first]=INT_MAX;
set<pair<int,string> > s;
dist[src]=0;
s.insert(make_pair(0,src));
while(!s.empty())
{
auto p=*(s.begin());
int nodedist=p.first;
string node=p.second;
s.erase(s.begin());
for(auto childnode: l[node])
{
if(nodedist+childnode.second< dist[childnode.first])
{
string dest= childnode.first;
auto f=s.find(make_pair(dist[dest],dest));
if(f!=s.end())
s.erase(f);
dist[dest]=nodedist+childnode.second;
s.insert(make_pair(dist[dest],dest));
}
}
}
}
void print()
{
for(auto p:l)
{
cout<<p.first<<" “;
for(auto l:p.second)
{
cout<<”("<<l.first<<","<<l.second<<") “;
}
cout<<endl;
}
}
};
int main()
{
Graphg;
g.addedge(“a”,“b”,1);
g.addedge(“a”,“c”,7);
g.addedge(“a”,“d”,3);
g.addedge(“b”,“c”,1);
g.addedge(“c”,“d”,2);
g.print();
cout<<” "<<endl;
g.dikstra(“a”);
g.print();
return 0;
}