Why this solution is giving wrong answer for first test case

general
, , ,
1

#include<bits/stdc++.h>
using namespace std;
#define ll long
#define mp make_pair
#define sc(x) scanf("%ld",&x)
#define ii pair<ll,ll>
#define pb push_back
#define INF INT_MAX
ll n;int e,source;
const int sz=100009;
vector g[100009];
ll dis[100009];
bool vis[100009];
void Dijkstra(ll source, ll n)
{
for(ll i=0;i<=n;++i)
vis[i]=0;
for(ll i=0;i< sz;i++)
dis[i]=INF;
class prioritize{public: bool operator ()(pair<int, int>&p1 ,pair<int, int>&p2){return p1.second>p2.second;}};
priority_queue<pair<int,int> ,vector<pair<int,int> >, prioritize> pq;
pq.push(mp(source,dis[source]=0));
while(!pq.empty())
{
pair<int, int> curr=pq.top();
pq.pop();
ll cv=curr.first,cw=curr.second;
if(vis[cv])
continue;
vis[cv]=true;
for(ll i=0;i< g[cv].size();i++)
if(!vis[g[cv][i].first] && g[cv][i].second+cw< dis[g[cv][i].first])
pq.push(make_pair(g[cv][i].first,(dis[g[cv][i].first]=g[cv][i].second+cw)));
}
for(ll i=1;i<=n;++i)
cout<< dis[i]<<" ";
}

    int main()
    {   ll tc,k,x,m,i,j;
        sc(tc);
        while(tc--)
        {sc(n);sc(k);sc(x);sc(m);sc(source);
        for(i=1;i<=sz;++i)
        g[i].clear();
     for(i=1;i<=k;++i)
    {
        for(j=1;j<=k;++j)
        {
            if(i!=j)
            g[i].pb(mp(j,x));
        }
    }
       while(m--)
    {
        sc(i);sc(j);sc(k);
        g[i].pb(mp(j,k));
        g[j].pb(mp(i,k));
    }

    Dijkstra(source,n);
    
    cout<<"\n";
        }
    	return 0;
    }
1 Like
2

That’s because you have pushed make_pair(vertex,dis[vertex]) in the min-priority queue . You should do it as push(make_pair(dis[vertex],vertex)) so that you pop out the vertex with minimum distance .
P.S. - you can also use multiset for the same purpose as min-priority queue . Try it sometimes … cheers … Also do upvote my answer as i need to ask some questions but don’t have enough karma .

3 Likes
3

Fixed the formatting.