This code fails in some test case giving WA.
I am unable to debug .Please help…/
/*
20
10 11 11
2 3 5
2 6 3
2 1 4
2 4 2
5 2 3
4 6 2
3 4 6
3 4 6
2 3 5
3 4 6
6 4 5
1 2 4
1 3 8
1 4 1
1 4 4
4 2 3
3 4 2
2 4 1
3 4 2
3
5
8
6
2
4
5
*/
It is failing here in the last query giving 6 but answer should be 8.Why is it so??
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x);
#define MOD 10000000
#define ll long long int
const int NMAX=505;
const int INF=1e7;
int N,M; // Vertices N and edges M
priority_queue<pair<int,int>, vector <pair<int,int> >, greater<pair<int ,int>>> q;
vector <pair<int,int >> adj[NMAX];
int dis[NMAX];
int parent[NMAX];
bool vis[NMAX];
int start_vertex;
int Q;
void dijkstra()
{
// Setting the distance array to be +infinity
for (int i=0;i< NMAX;i++)
dis[i]=INF;
for (int i=0;i<NMAX;i++)
vis[i]=false;
dis[start_vertex]= 0;
parent[start_vertex]= -1;
vis[start_vertex]= true;
q.push({dis[start_vertex],start_vertex});
while (!q.empty())
{
int d=q.top().first;
int u=q.top().second;
q.pop();
if (d!=dis[u])
continue;
for (int i=0;i<adj[u].size();i++)
{
int v=adj[u][i].first;
int prio=dis[u] + adj[u][i].second;
if ( !vis[v] && dis[v] > prio)
{
dis[v]= prio;
parent[v]= u;
q.push({dis[v], v});
}
}
vis[u]=true;
}
}
int main()
{
cin >> M;
while (M--)
{
int a,b,w;
cin >> a>> b >> w;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
cin >> start_vertex;
dijkstra();
cin >> Q;
for (int i=0;i<Q;i++)
{
int V;
cin >> V;
if (dis[V]!=1e7)
cout << dis[V] << endl;
else
cout << "NO PATH";
}
}
