//Copyright@Souhardya
//Question : Djikstra
#include
using namespace std;
#define pb push_back
#define mk make_pair
#define f first
#define se second
#define ll long long int
#define ld long double
#define MOD 1000000007
//Same aprroach works for directed||undirected
ll mindist(ll *dist,ll *vis,ll n)
{
ll mn=INT_MAX; ll ind=-1;
for(ll i=0;i>&v)
{
ll vis[n]={0}; ll dist[n];
for(ll i=0;i>> &v)
{
ll vis[n]={0}; ll dist[n];
for(ll i=0;i,vector>,greater>>q;
q.push(mk(0,src));
while(!q.empty())
{
ll id=(q.top()).se;
q.pop();
vis[id]=1;
for(ll i=0;idist[id]+ds)
{
dist[tar]=dist[id]+ds;
q.push(mk(dist[tar],tar));
}
}
}
for(ll i=0;i>n>>e;
ll src;
cin>>src;
//Adjacent Matrix approach's vector
vector>v(n,vector(n,0));
//Adjacent list approach's vector
vector>>v2(n);
for(ll i=0;i>x>>y>>w;
//Vector matrix
v[x][y]=w;
v[y][x]=w;
//List matrix
v2[x].pb(mk(y,w));
v2[y].pb(mk(x,w));
}
//Adjacent vector approach
cout<<"Adjacent Matrix Form:"<