2949903_ac_296ms_2452k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 55 行

import java.util.*;

public class Main
{

	public static void main(String[] args) 
        {
	
            int Inf = 1000000;
            int i, j, n, k, t, a, b, cas;
            Scanner cin = new Scanner (System.in);
        
            cas = 1;
            while(cin.hasNext())
            {
                System.out.println("Test Set #"+cas);
                cas++;
                int map[][] = new int [21][21];
                for(i = 1; i <= 20; i++)
                    for(j = 1; j <= 20; j++)
                        map[i][j] = Inf;
                for(i = 1; i <= 19; i++)
                {
                    n = cin.nextInt();
                    for(j = 1; j <= n; j++)
                    {
                        t = cin.nextInt();
                        map[i][t] = map[t][i] = 1;
                    }
                }
                for(k = 1; k <= 20; k++)
                {
                    for(i = 1; i <= 20; i++)
                    {
			if(map[i][k]!=Inf)
			{
				for(j = 1; j <= 20; j++)
					if(map[i][k]+map[k][j]<map[i][j])
						map[i][j]=map[i][k]+map[k][j]; 
			}
                    }  
                }
                n = cin.nextInt();
                for(i = 0; i < n; i++)
                {
                    a = cin.nextInt();
                    b = cin.nextInt();
                    System.out.println(a+" to "+b+": "+map[a][b]); 
                }
                System.out.println();
            }
        }
}