// Slower than boas_scanner in two ways: // - No precomputation is done for the calculation of minCost // - A DFS is called for every starting station instead of just once import java.util.*; class Pair, T extends Comparable> implements Comparable> { S first; T second; Pair(S f, T s) { first = f; second = s; } @Override public int compareTo(Pair o) { int t = first.compareTo(o.first); if (t == 0) return second.compareTo(o.second); return t; } @Override public int hashCode() { return (31 + first.hashCode()) * 31 + second.hashCode(); } @Override public boolean equals(Object o) { if (!(o instanceof Pair)) return false; if (o == this) return true; Pair p = (Pair) o; return first.equals(p.first) && second.equals(p.second); } @Override public String toString() { return "Pair{" + first + ", " + second + "}"; } } public class boas_100_dfs_scanner { static HashMap>> adjList = new HashMap<>(); static HashMap people = new HashMap<>(); static int n; static int m; static int p; static int g; static HashMap>> dagAdjList; static HashSet visited = new HashSet<>(); static HashMap dijkstra(int source) { HashMap dist = new HashMap<>(); for(int i=0; i> pq = new PriorityQueue<>(); pq.add(new Pair<>(dist.get(source), source)); while(!pq.isEmpty()) { Pair node = pq.remove(); long cost = node.first; int from = node.second; if(cost > dist.get(from)) continue; for(Pair neighbour : adjList.get(from)) { int to = neighbour.first; long newCost = dist.get(from) + neighbour.second; if(newCost < dist.get(to)) { dist.put(to, newCost); pq.add(new Pair<>(newCost, to)); } } } return dist; } static HashMap>> shortestPathDAG(HashMap dist) { HashMap>> ldagAdjList = new HashMap<>(); for(int i=0; i()); } for(int node=0; node neighbour : adjList.get(node)) { if(dist.get(node) + neighbour.second <= dist.get(neighbour.first)) { ldagAdjList.get(neighbour.first).add(new Pair<>(node, neighbour.second)); } } } return ldagAdjList; } static HashMap peopleAlongRoute = new HashMap<>(); static void dfs(int node, int person) { peopleAlongRoute.get(node).set(person, true); for(Pair neighbour : dagAdjList.get(node)) { if(!visited.contains(neighbour.first)) { visited.add(neighbour.first); dfs(neighbour.first, person); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); p = sc.nextInt(); g = sc.nextInt(); for(int i=0; i stationsForPeople = new HashMap<>(); for(int i=0; i()); } for(int i=0; i(b, c)); adjList.get(b).add(new Pair<>(a, c)); } HashMap dist = dijkstra(0); dagAdjList = shortestPathDAG(dist); for(int i=0; i(); dfs(stationsForPeople.get(i), i); } long separateCost = 0; for(int i=0; i