Cerinta completa

Consider an undirected graph containing nodes and edges. Each edge has an integer cost, , associated with it.

The penalty of a path is the bitwise OR of every edge cost in the path between a pair of nodes, and . In other words, if a path contains edges , then the penalty for this path is OR OR … OR .

Given a graph and two nodes, and , find the path between and having the minimal possible penalty and print its penalty; if no such path exists, print to indicate that there is no path from to .

Note: Loops and multiple edges are allowed. The bitwise OR operation is known as or in Pascal and as | in C++ and Java.

Input Format

The first line contains two space-separated integers, (the number of nodes) and (the number of edges), respectively.

Each line of the subsequent lines contains three space-separated integers , , and , respectively, describing edge connecting the nodes and and its associated penalty ().

The last line contains two space-separated integers, (the starting node) and (the ending node), respectively.

Constraints

Output Format

Print the minimal penalty for the optimal path from node to node ; if no path exists from node to node , print .

Sample Input

3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3

Sample Output

3

Explanation

The optimal path is .
and .
The penalty for this path is: OR , so we print .

Limbajul de programare folosit: java8

Cod:

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

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.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 <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

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

    private static class State {
        int node, mask;
        State(int node, int mask) { this.node = node; this.mask = mask; }
    }

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

        @SuppressWarnings("unchecked")
        ArrayList<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 c = fs.nextInt();
            g[u].add(new Edge(v, c));
            g[v].add(new Edge(u, c));
        }

        int a = fs.nextInt();
        int b = fs.nextInt();

        final int MAX_MASK = 1 << 11; // c_i <= 1023 for this challenge
        boolean[][] seen = new boolean[n + 1][MAX_MASK];
        ArrayDeque<State> q = new ArrayDeque<>();

        seen[a][0] = true;
        q.add(new State(a, 0));

        while (!q.isEmpty()) {
            State cur = q.poll();
            for (Edge e : g[cur.node]) {
                int nm = cur.mask | e.w;
                if (nm >= MAX_MASK) continue;
                if (!seen[e.to][nm]) {
                    seen[e.to][nm] = true;
                    q.add(new State(e.to, nm));
                }
            }
        }

        int ans = -1;
        for (int mask = 0; mask < MAX_MASK; mask++) {
            if (seen[b][mask]) {
                ans = mask;
                break;
            }
        }

        System.out.println(ans);
    }
}

Scor obtinut: 1.0

Submission ID: 464616783

Link challenge: https://www.hackerrank.com/challenges/beautiful-path/problem

Minimum Penalty Path