白駿-1976号旅行に行きましょう

方法

最後の行A->B->D...このように旅行に行きたい場所、訪問した場所、最短距離を歩く必要はありません.だから.

このように考える.

ソース

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

public class Main {
	static int N;
	static int M;
	static int[][] ADJ;
	static boolean[] VISIT;
	static ArrayList<ArrayList<Integer>> LIST;
	static int[] INDEX;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		ADJ = new int[N][N];
		VISIT = new boolean[N];
		INDEX = new int[N];
		
		Arrays.fill(INDEX, -1);
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				int num = Integer.parseInt(st.nextToken());
				ADJ[i][j] = num;
			}
		}
		
		LIST = new ArrayList<ArrayList<Integer>>();
		
		for(int i = 0; i < N; i++) {
			if(!VISIT[i]) makeGraph(i);
		}
		
		ArrayList<Integer> travel = new ArrayList<Integer>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			travel.add(Integer.parseInt(st.nextToken())-1);
		}
		
		int groupNum = INDEX[travel.get(0)];
		for(int i = 1; i < travel.size(); i++) {
			if(groupNum != INDEX[travel.get(i)]) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
		
		
		
	}
	static void makeGraph(int idx) {
		ArrayList<Integer> graph = new ArrayList<Integer>();
		graph.add(idx);
		VISIT[idx] = true;

		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(idx);
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			for(int i = 0; i < N; i++) {
				//방문아직 안하고, 연결된 경우
				if(!VISIT[i] && ADJ[cur][i] == 1) {
					q.offer(i);
					VISIT[i] = true;
					graph.add(i);
				}
			}						
		}	
		LIST.add(graph);
		for(int i = 0; i < graph.size(); i++) {
			INDEX[graph.get(i)] = LIST.size();
		}
	}
}