阿祁的部落格

ZeroJudge e792 - 旅行 解題心得( 題目 )

解題概念:Floyd-Washwall algorithm

解題方法:這題是TOI的題目，注意這題很多查詢，所以顯然不能一直 DFS，我們可以把題目視作一個查詢最短路徑的題目，假設每個連通的點都是0，沒聯通的是1，這樣可以透過Floyd algorithm以時間O(n^3)建表，這樣可以達到O(1)的單筆查詢複雜度。

Java參考程式碼 (有更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2022/1/12

import java.io.*;

public class zje792 {

    public static int ret,r,n,m,q;

      public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static int[][] dis=new int[205][205];

    public static void main(String[] args) throws Exception{

        n=readint();

        m=readint();

        q=readint();

        init();

        for(int i=0;i<m;i++) {

            dis[readint()][readint()]=0;

        }

        floyd();

        for(int i=0;i<q;i++) {

            bw.write((dis[readint()][readint()]==0)?"YES\n":"NO\n");

        }

        bw.flush();

    }

    

    public static void init() {

        for(int i=0;i<205;i++) {

            for(int j=0;j<205;j++) {

                dis[i][j]=1;

            }

        }

    }

    

    public static void floyd() {

        for(int k=0;k<n;k++) {

            for(int i=0;i<n;i++) {

                for(int j=0;j<n;j++) {

                    dis[i][j]=Math.min(dis[i][j],dis[i][k]+dis[k][j]);

                }

            }

        }

    }

    

      public static int readint() throws Exception {

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}