#include <bits/stdc++.h>
#include
#include
#include
#include <unordered_map>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template
class graph{
map<T,list<pair<T,int>>> adjlist;
public:
void addedge(T u , T v , int dist, bool bidir = true){
adjlist[u].push_back(make_pair(v,dist));
if(bidir){
adjlist[v].push_back(make_pair(u,dist));
}
}
void display(){
for(auto j:adjlist){
cout<<j.first<<"->";
for(auto val:j.second){
cout<<"("<<val.first<<"-"<<val.second<<")";
}
cout<<endl;
}
}
void dijstaraalgo(T src){
map<T,int> dist;
for(auto j:adjlist){
dist[j.first] = INT_MAX;
}
set<pair<int,T>> s;
dist[src] =0;
s.insert(make_pair(0,src));
while(!s.empty()){
auto p = *(s.begin());
T node =p.second;
int nodedis = p.first;
s.erase(s.begin());
for(auto neighbor:adjlist[node]){
if(nodedis + neighbor.second<dist[neighbor.first]){
T dest = neighbor.first;
auto f = s.find(make_pair(dist[dest],dest));
if(f!=s.end()){
s.erase(f);
}
dist[dest] = nodedis + neighbor.second;
s.insert(make_pair(dist[dest],dest));
}
}
}
for(auto d:dist){
if(d.first!=src){
cout<<d.second<<" ";
}
if(d.second == INT_MAX){
cout<<"-1 ";
}
}
}
};
int main(){
int t;
cin>>t;
while(t–){
graph g;
int n,m;
cin>>n>>m;
while(m–){
int x,y,r;
cin>>x>>y>>r;
g.addedge(x,y,r);
}
int s;
cin>>s;
g.dijstaraalgo(s);
cout<<endl;
}
return 0;
}
this is my code i am unable to pass the testcase for the dijkstra problem; kindly please help me and fix it ;