Codeforces Beta Round #55 Div2 E. Shortest Path

問題

社内の勉強会で出題された。

http://codeforces.com/contest/59/problem/E

N 個の頂点と M 本の重み 1 の無向辺からなるグラフがある。K 個の (a, b, c) の組が与えられる。各 (a, b, c) について a, b, c の順で連続して頂点を通ることができないとした時、1 から N までの最短距離とその経路を求めよ。

解法

各頂点 v について幅優先するのではなく、v の 1 個前の頂点 p と合わせて、(p, v) を 1 つの頂点と考えて幅優先する。例えば、x->y->z という経路を通るとき、(x, y) から (y, z) に移動するイメージである。(a, b) から (b, c) へ移動しないようにしながら BFS して距離を出す。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

public class E {
  private static class Task {

    void solve(FastScanner in, PrintWriter out) {
      int N = in.nextInt();
      int M = in.nextInt();
      int K = in.nextInt();
      ArrayList<Integer>[] graph = new ArrayList[N];
      for (int i = 0; i < N; i++) {
        graph[i] = new ArrayList<>();
      }

      for (int i = 0; i < M; i++) {
        int v = in.nextInt() - 1, u = in.nextInt() - 1;
        graph[v].add(u);
        graph[u].add(v);
      }

      //<a*N+b, [c]>
      TreeMap<Integer, TreeSet<Integer>> triples = new TreeMap<>();
      for (int i = 0; i < K; i++) {
        int a = in.nextInt() - 1;
        int b = in.nextInt() - 1;
        int c = in.nextInt() - 1;

        int key = a * N + b;
        TreeSet<Integer> cs = triples.get(key);
        if (cs == null) triples.put(key, cs = new TreeSet<>());
        cs.add(c);
      }

      ArrayDeque<Integer> deque = new ArrayDeque<>();
      int[][] dist = new int[N][N];
      for (int[] d : dist) Arrays.fill(d, Integer.MAX_VALUE);
      deque.add(0);
      dist[0][0] = 0;
      outer:
      while (!deque.isEmpty()) {
        Integer key = deque.poll();
        int v = key % N;// now
        int p = key / N;// parent
        for (int next : graph[v]) {
          if (triples.containsKey(key) && triples.get(key).contains(next)) continue;
          if (dist[v][next] > dist[p][v] + 1) {
            dist[v][next] = dist[p][v] + 1;
            deque.add(v * N + next);
            if (next == N - 1) break outer;
          }
        }
      }

      int min = Integer.MAX_VALUE;
      for (int i = 0; i < N; i++) min = Math.min(min, dist[i][N - 1]);
      if (min == Integer.MAX_VALUE) {
        out.println(-1);
        return;
      }

      out.println(min);
      ArrayList<Integer> ans = new ArrayList<>();
      int cur = N - 1;
      while (cur > 0) {
        ans.add(cur + 1);
        for (int v : graph[cur]) {
          if (dist[v][cur] == min) {
            cur = v;
            min--;
            break;
          }
        }
      }
      Collections.reverse(ans);
      out.print(1);
      for (int v : ans) {
        out.print(" " + v);
      }
      out.println();

    }
  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }
  }
}