We Learn   We Create   We Share

初学者指南
笔记
竞赛
关于我们
页面搜索

目录

AtCoder D 209

AtCoder

Leon | 25 Jul 2021

题目描述

Takahashi王国有N条城并且城与城之间一共有N-1条路。第i条路连接ai和bi。所有的路都有相同的长度。

有Q个问题给你：

两个人分别在ci城与di城。他们两个将会互相通过最短路径渠道对方的城市，问他们是在路上相遇还是在城市里面相遇。

思路

先将所有的城市与0号城市的最短距离算出来（用BFS）

然后再将ci与di的与0号城市的最短路径相加，然后看看这个数的奇偶性，如果是偶数则在城市里相遇，反之则在路上相遇。

原理，因为ci与di的最短路径与ci与di的与0号城市的最短路径相加的奇偶性是相等的，因为除了最短路径之外的路都会走两遍，然而奇数加偶数等于奇数，偶数加偶数等于偶数，所以奇偶性不变。

复杂度分析： \(BFS：O(N^2)\)

\[traverse\space queries:O(N)\] \[overall\space complexity:O(N^2)\]

代码实现

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.*;
public class collision2{
    public static void main (String [] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int Q = in.nextInt();
        ArrayList<Integer> [] graph = new ArrayList[N];
        

        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < N-1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            graph[a-1].add(b-1);
            graph[b-1].add(a-1);
        }
        Queue<Integer> dp = new LinkedList<>();
        //Queue<Integer>dp = new LinkedList<>();
        int [] dis = new int [N];
        Arrays.fill(dis, -1);
        dp.add(0);
        while(!dp.isEmpty()){
            int pulling = dp.poll();
            for(int j:graph[pulling]){
                if(dis[j]==-1){
                    dis[j] = dis[pulling]+1;
                    dp.add(j);
                }
            }
        }

        for (int i = 0; i < Q; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            if(dis[a-1]%2!=dis[b-1]%2) System.out.println("Road");
            else System.out.println("Town");    
        }
    }
}

评论区