目錄

Floyd求最短路模板

4074. 鐵路與公路 - floyd + 腦筋急轉彎

Floyd求最短路模板

活動 - AcWing

題目：

給定一個 n?個點 m?條邊的有向圖，圖中可能存在重邊和自環(huán)，邊權可能為負數(shù)。

再給定 k 個詢問，每個詢問包含兩個整數(shù) x?和 y，表示查詢從點 x 到點 y 的最短距離，如果路徑不存在，則輸出 impossible

數(shù)據(jù)保證圖中不存在負權回路

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; //如果是自環(huán)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?小時的時間。
• 現(xiàn)在有一列火車和一輛汽車同時離開城市 1，它們的目的地都是城市 n。
• 它們不會在途中?？?#xff08;但是可以在城市 n ?？?#xff09;。
• 火車只能沿鐵路行駛，汽車只能沿公路行駛。
• 請你為它們規(guī)劃行進路線，每條路線中可重復經過同一條鐵路或公路，但是為了避免發(fā)生事故，火車和汽車不得同時到達同一個城市（城市 n?除外）。
• 請問，在這些條件的約束下，兩輛車全部到達城市 n 所需的最少小時數(shù)，即求更慢到達城市 n?的那輛車所需的時間的最小值。

思路：

由題目可知，公路和鐵路不會重合

那么必然有一輛車最短時間為1，因為1到n之間必然有一條路（公路或鐵路）

一輛車從1直接到n，另一輛走其他路，則兩車并不會在中途城市相遇

所以我們直接求兩者的最短路即可

由于數(shù)據(jù)范圍較小，我們用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;}
}

?