C.cpp

#include <bits/stdc++.h>
using namespace std;


#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i < n; i++)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))
#define PI 3.1415926535897932385
#define uint64 unsigned long long
#define Int long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define ff first
#define ss second
#define bit(n) (1<<(n))
#define Last(i) ( (i) & (-i) )
#define sq(x) ((x) * (x))
#define INF INT_MAX
#define mp make_pair


Int  k ;
Int  G ;


void  bfs( Int v , Int n  , vector<vector<Int> >&g ,  vector<set<Int> >&affect )
 {


   vector<bool> visit( n , false ); // initialising the visit vector

   queue<pair<Int,Int> > q ; // queue for running the bfs  < vertex ,  height >
   q.push( mp(v,0)  ) ; //  initialised by pushing the gangster node in the queue


   while( !q.empty ( ) )
    {
         pair<Int,Int> tp ;

         tp  =  q.front( );
         q.pop() ;
         v = tp.ff ; // storing the current vertex
         Int h = tp.ss ; // storing the height of the vertex
         if( visit[v] )continue ;
         visit[v] = true   ;

         if( h <= k ){  affect[v].insert(G) ; } // if height less than the max are of influence



        for( Int i = 0 ; i < g[v].size() ; i ++ )
         {

            Int ch = g[v][i] ;
            if( !visit[ch] )
            q.push( mp( ch ,  h + 1 ) ) ; // inserting the child nodes into the queue whith updated heights

         }

    }

 }


set<Int> include  ;  // This is a set which stores the all the gangsters to whom we have paid our debts till now .
// We keep on adding more gangsters to the list as we try to move on cheapest path

Int djkstra( Int s , Int en , vector<vector<Int> > &g ,  vector<Int>&gang , Int n , vector<set<Int> >& affect )
{
    include.clear() ; // clearing the include meaning that there are no gangsters who we have paid debts till now

   	vector<Int> d (n, 1e15 ); // initialising the distance array with INF

          d[s] = 0 ;  // Updating the cost of source by adding the cost of all gangsters who are in are of influence
	        for( set<Int>::iterator it = affect[s].begin(); it!= affect[s].end() ; it ++ )
	                { d[s]  += gang[*it] ;}



	set < pair<Int,Int> > q;  // maintaing the set for djkstra which stores the < min_distance , vertex  >
	q.insert (make_pair (d[s], s)); // inserting the source vertex into the set

	while (!q.empty()) {

	Int v = q.begin()->second;


  // Now we are including all the gangsters to whom we have already paid and we need not pay them again
	for( set<Int>::iterator it = affect[v].begin() ; it!= affect[v].end() ; it++ )
                     include.insert(*it);



	q.erase (q.begin());

	for (size_t j=0; j<g[v].size(); ++j) {

        Int to = g[v][j]; // looking at all the neighbouring vertexes

        // erasing all the gangsters who we have paid till now from the list of gangsters who affect the neighbouring vertex
		    for( set<Int>::iterator it = include.begin() ; it!= include.end() ;it ++  )
                   { if( affect[to].find(*it) != affect[to].end()  )
                         affect[to].erase(*it) ; }

           Int len = 0 ;
        // calculating the actual cost of including this vertex
        for( set<Int>::iterator it = affect[to].begin(); it!= affect[to].end() ; it ++ )
                       len += gang[*it] ;


      // Relaxing the nodes
	   		if (d[v] + len < d[to]) {
		  		q.erase (make_pair (d[to], to));
			  	d[to] = d[v] + len;
				  q.insert (make_pair (d[to], to));
			}
		                                          }

		}

   return d[en]  ;
}

int  main( )
{
    Int  n , m , p ;
    cin >> n >> m >> p >> k ; // number of nodes ,edges, gangs , distance
    vector<Int>gang( p  ) ; // storing the weights of gangs
    vector<Int>loc ( p ) ;  // storing the vertex of the gang
    vector< set< Int>  > affect( n ) ;  //storing which gangs affect a perticular vertex

    for( Int  i = 0 ; i < p ; i ++ )
      { cin >> loc[i];
        loc[i] -- ; }

    for(  Int i = 0 ; i < p ; i ++ )
       cin >>  gang[i] ;


     vector<vector<Int> > g( n ) ; // initialising the graph

     for( Int  i = 0 ; i < m  ; i ++ )
      {
         Int a ,  b ;
         cin >> a ;
         cin >> b ;
         a--;  // done for zero based indexing
         b-- ;
         g[a].pb(b) ; // making undirected edges in the graph
         g[b].pb(a) ;

      }

      Int st , en  ;
      cin >>  st >> en  ;
      st -- ;  // done for zero based indexing
      en -- ;



     for ( Int  i = 0 ; i < p ;  i ++ )
       {
          G = i ; // setting the current gangster index for future refernce
          bfs( loc[i] , n , g  , affect ) ; // running  a bfs on each of the gangs and updating the nodes which are under influence of gang

       }



    cout<<  djkstra( st , en ,  g , gang ,n, affect )<<endl;  // running the djkstra for finding the shortest path



}