[UVa] 13127 – Bank Robbery

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13127 – Bank Robbery
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Dijkstra Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define inf                1234567890
 
static const int maxn = 1e3 + 5;
 
struct node
{
      int v, w;
      node(int v = 0, int w = 0) : v(v), w(w) {}
      inline bool operator < (const node &p) const
      {
            return w > p.w;
      }
};
 
vector <node> graph[maxn];
int dist[maxn];
int tsites, troad, tbank, tpoliceStation;
vector <int> bank, policeStation, ans;
 
inline void dijkstra()
{
      for (int i = 0; i < maxn; i++) dist[i] = inf;
      priority_queue <node> PQ;
      for (int p : policeStation)
      {
            PQ.emplace(p, 0);
            dist[p] = 0;
      }
      while (!PQ.empty())
      {
            node u = PQ.top(); PQ.pop();
            for (node v : graph[u.v])
            {
                  if (dist[v.v] > dist[u.v] + v.w)
                  {
                        dist[v.v] = dist[u.v] + v.w;
                        PQ.emplace(v.v, dist[v.v]);
                  }
            }
      }
}
 
inline void clean()
{
      bank.clear();
      policeStation.clear();
      ans.clear();
      for (int i = 0; i < maxn; i++) graph[i].clear();
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      while (cin >> tsites >> troad >> tbank >> tpoliceStation)
      {
            clean();
            for (int e = 0; e < troad; e++)
            {
                  int u, v, w;
                  cin >> u >> v >> w;
                  graph[u].emplace_back(v, w);
                  graph[v].emplace_back(u, w);
            }
            for (int i = 0; i < tbank; i++)
            {
                  int u;
                  cin >> u;
                  bank.emplace_back(u);
            }
            sort(bank.begin(), bank.end());
            for (int i = 0; i < tpoliceStation; i++)
            {
                  int u;
                  cin >> u;
                  policeStation.emplace_back(u);
            }
            dijkstra();
            int maxDistance = -1;
            for (int b : bank) if (dist[b] > maxDistance) maxDistance = dist[b];
            int cnt = 0;
            for (int b : bank) if (dist[b] == maxDistance) cnt++, ans.emplace_back(b);
            cout << cnt;
            if (maxDistance == inf) cout << " *\n";
            else cout << " " << maxDistance << endl;
            for (int i = 0; i < cnt; i++)
            {
                  cout << ans[i];
                  if (i + 1 == cnt) cout << endl;
                  else cout << " ";
            }
      }
}