my code is working fine in sampe cases and other cases even on submission it is giving wrong ans
#include <bits/stdc++.h>
using namespace std;
template
class graph{
unordered_map<T,list<pair<T,int> > >m;
public:
void addEdge(T x,T y,int w ){
m[x].push_back(make_pair(y,w));
m[y].push_back(make_pair(x,w));
}
void dijakstra(int src)
{
unordered_map<T,int>dis;
//set all distances to infinnity
for(auto x:m){
dis[x.first]=INT_MAX;
}
//make a set to find out a node with min distance
set<pair<int,T> >s;
dis[src]=0;
s.insert(make_pair(0,src));
while(!s.empty())
{
auto p=*(s.begin());
T node=p.second;
int node_dis=p.first;
s.erase(s.begin());
//iterate over neighbour children of current node
for(auto child:m[node])
{
if(node_dis + child.second < dis[child.first])
{
//we have to update it
//we have to remove the old pair and insert the new pair to simulate updation
T des=child.first;
auto f=s.find(make_pair(dis[des],des));
if(f!=s.end()){
s.erase(f);
}
//insert the new pair
dis[des]=node_dis + child.second;
s.insert(make_pair(dis[des],des));
}
}
}
//now print distance to all other node
for(auto d:dis)
{
if(d.first!=src){
if(d.second!=INT_MAX){
cout<<d.second<<" ";
}
else{
cout<<"-1"<<" ";
}
}
}
}
};
int main() {
graph g;
int t,n,m;
cin>>t;
while(t–)
{
int src;
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,w;
cin>>x>>y>>w;
g.addEdge(x,y,w);
}
cin>>src;
g.dijakstra(src);
cout<<endl;
}
return 0;
}
