【蓝桥杯集训16】多源汇求最短路——Floyd算法（2 / 2）

目录

Floyd求最短路模板

4074. 铁路与公路 - floyd + 脑筋急转弯

---

Floyd求最短路模板

活动 - AcWing

题目：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible

数据保证图中不存在负权回路

public static void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=Math.min(d[i][j],d[i][k]+d[k][j]);}

/**道阻且长，行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N=210;static int n,m,k;static int[][] d=new int[N][N];public static void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=Math.min(d[i][j],d[i][k]+d[k][j]);}public static void main(String[] args) throws IOException{n=rd.nextInt();m=rd.nextInt();k=rd.nextInt();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) d[i][j]=0; //如果是自环else d[i][j]=0x3f3f3f3f;while(m-->0){int a=rd.nextInt(),b=rd.nextInt(),w=rd.nextInt();d[a][b]=Math.min(d[a][b],w); //重边取最小}floyd();while(k-->0){int x=rd.nextInt(),y=rd.nextInt();if(d[x][y]>0x3f3f3f3f/2) wt.println("impossible");else wt.println(d[x][y]);}wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}

4074. 铁路与公路 - floyd + 脑筋急转弯

4074. 铁路与公路 - AcWing题库

题目：

• 某国家有 n 个城市（编号 1∼n）和 m 条双向铁路
• 对于每对不同的城市 x,y，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。
• 经过每条铁路或公路都需要花费 1 小时的时间。
• 现在有一列火车和一辆汽车同时离开城市 1，它们的目的地都是城市 n。
• 它们不会在途中停靠（但是可以在城市 n 停靠）。
• 火车只能沿铁路行驶，汽车只能沿公路行驶。
• 请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 n 除外）。
• 请问，在这些条件的约束下，两辆车全部到达城市 n 所需的最少小时数，即求更慢到达城市 n 的那辆车所需的时间的最小值。

思路：

由题目可知，公路和铁路不会重合

那么必然有一辆车最短时间为1，因为1到n之间必然有一条路（公路或铁路）

一辆车从1直接到n，另一辆走其他路，则两车并不会在中途城市相遇

所以我们直接求两者的最短路即可

由于数据范围较小，我们用floyd算法（O(n^3))

/**道阻且长，行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N=410;static int n,m;static int[][] tr=new int[N][N];static int[][] car=new int[N][N];public static int floyd(int[][] d){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) d[i][j]=Math.min(d[i][j],d[i][k]+d[k][j]);return d[1][n];}public static void main(String[] args) throws IOException{n=rd.nextInt();m=rd.nextInt();for(int i=1;i<=n;i++) Arrays.fill(tr[i],0x3f3f3f3f);for(int i=1;i<=n;i++) Arrays.fill(car[i],0x3f3f3f3f);while(m-->0){int a=rd.nextInt(),b=rd.nextInt();tr[a][b]=tr[b][a]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(tr[i][j]!=1&&i!=j) car[i][j]=car[j][i]=1;int a=floyd(tr);int b=floyd(car);int res=Math.max(a,b);if(res==0x3f3f3f3f) wt.print(-1);else wt.print(res);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}class PII
{int x,y;PII(int x,int y){this.x=x;this.y=y;}
}