Soluție HackerRank pentru Synchronous Shopping. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Synchronous Shopping

Cerinta completa

Bitville is a seaside city that has a number of shopping centers connected by bidirectional roads, each of which has a travel time associated with it. Each of the shopping centers may have a fishmonger who sells one or more kinds of fish. Two cats, Big Cat and Little Cat, are at shopping center (each of the centers is numbered consecutively from to ). They have a list of fish they want to purchase, and to save time, they will divide the list between them. Determine the total travel time for the cats to purchase all of the types of fish, finally meeting at shopping center . Their paths may intersect, they may backtrack through shopping center , and one may arrive at a different time than the other. The minimum time to determine is when both have arrived at the destination.

For example, there are shopping centers selling types of fish. The following is a graph that shows a possible layout of the shopping centers connected by paths. Each of the centers is labeled . Here and represent Big Cat and Little Cat, respectively. In this example, both cats take the same path, i.e. and arrive at time having purchased all three types of fish they want. Neither cat visits shopping centers or .

image

Function Description

Complete the shop function in the editor below. It should return an integer that represents the minimum time required for their shopping.

shop has the following parameters:
– n: an integer, the number of shopping centers
– k: an integer, the number of types of fish
– centers: an array of strings of space-separated integers where the first integer of each element is the number of types of fish sold at a center and the remainder are the types sold
– roads: a 2-dimensional array of integers where the first two values are the shopping centers connected by the bi-directional road, and the third is the travel time for that road

Input Format

The first line contains space-separated integers: (the number of shopping centers), (the number of roads), and (the number of types of fish sold in Bitville), respectively.

Each line of the subsequent lines () describes a shopping center as a line of space-separated integers. Each line takes the following form:

  • The first integer, , denotes the number of types of fish that are sold by the fishmonger at the shopping center.
  • Each of the subsequent integers on the line describes a type of fish sold by that fishmonger, denoted by , where going forward.

Each line of the subsequent lines () contains space-separated integers that describe a road. The first two integers, and , describe the two shopping centers it connects. The third integer, , denotes the amount of time it takes to travel the road.

Constraints

  • All are different for every fixed .
  • Each road connectes distinct shopping centers (i.e., no road connects a shopping center to itself).
  • Each pair of shopping centers is directly connected by no more than road.
  • It is possible to get to any shopping center from any other shopping center.
  • Each type of fish is always sold by at least one fishmonger.

Output Format

Print the minimum amount of time it will take for the cats to collectively purchase all fish and meet up at shopping center .

Sample Input

5 5 5
1 1
1 2
1 3
1 4
1 5
1 2 10
1 3 10
2 4 10
3 5 10
4 5 10

Sample Output

30

Explanation

image
represents a location Big Cat visits, represents a location where Little Cat visits.

Big Cat can travel and buy fish at all of the shopping centers on his way.

Little Cat can then travel , and buy fish from the fishmonger at the shopping center only.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ');
            int sgn = 1;
            if (c == '-') { sgn = -1; c = read(); }
            int x = 0;
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    static class Edge {
        int to, w;
        Edge(int to, int w) { this.to = to; this.w = w; }
    }

    static class State implements Comparable<State> {
        long d;
        int node, mask;
        State(long d, int node, int mask) { this.d = d; this.node = node; this.mask = mask; }
        public int compareTo(State o) { return Long.compare(this.d, o.d); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        int k = fs.nextInt();

        int[] cityMask = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int t = fs.nextInt();
            int mask = 0;
            for (int j = 0; j < t; j++) {
                int fish = fs.nextInt() - 1;
                mask |= (1 << fish);
            }
            cityMask[i] = mask;
        }

        List<Edge>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = fs.nextInt();
            int v = fs.nextInt();
            int w = fs.nextInt();
            g[u].add(new Edge(v, w));
            g[v].add(new Edge(u, w));
        }

        int S = 1 << k;
        long INF = Long.MAX_VALUE / 4;
        long[][] dist = new long[n + 1][S];
        for (int i = 1; i <= n; i++) Arrays.fill(dist[i], INF);

        PriorityQueue<State> pq = new PriorityQueue<>();
        int startMask = cityMask[1];
        dist[1][startMask] = 0;
        pq.add(new State(0, 1, startMask));

        while (!pq.isEmpty()) {
            State cur = pq.poll();
            if (cur.d != dist[cur.node][cur.mask]) continue;
            for (Edge e : g[cur.node]) {
                int nm = cur.mask | cityMask[e.to];
                long nd = cur.d + e.w;
                if (nd < dist[e.to][nm]) {
                    dist[e.to][nm] = nd;
                    pq.add(new State(nd, e.to, nm));
                }
            }
        }

        int full = S - 1;
        long ans = INF;
        for (int a = 0; a < S; a++) {
            if (dist[n][a] >= INF) continue;
            for (int b = a; b < S; b++) {
                if ((a | b) == full && dist[n][b] < INF) {
                    long cand = Math.max(dist[n][a], dist[n][b]);
                    if (cand < ans) ans = cand;
                }
            }
        }

        System.out.print(ans);
    }
}

Scor obtinut: 1.0

Submission ID: 464610676

Link challenge: https://www.hackerrank.com/challenges/synchronous-shopping/problem

Synchronous Shopping