第一行为两个整数,结点数,边数
第二行到第m+1行各有3个数分别为:结点u,结点v,需要的时间段
最后一行为出发结点和到达结点
4 4 1 2 5 1 3 6 2 4 8 3 4 6 1 4 示例输出12 4 4 1 2 25 1 3 18 2 4 28 3 4 22 1 4 7.9/8 示例输出40
BFS(参考迪杰斯特拉算法)
参考链接:https://blog.csdn.net/yu121380/article/details/79810233
public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ String[] arr1 = line.split(" "); int n = Integer.parseInt(arr1[0]); int m = Integer.parseInt(arr1[1]); //邻接矩阵 int[][] arr = new int[n+1][n+1]; //距离数组 int[] dis = new int[n+1]; //已拜访数组 boolean[] vis = new boolean[n+1]; for(int i = 0;i < n+1;i++){ dis[i] = Integer.MAX_VALUE; vis[i] = false; for(int j = 0;j < n+1;j++){ arr[i][j] = Integer.MAX_VALUE; } } //构建邻接矩阵,除了连通的地方其他的都为int的最大值 for(int i = 0;i < m;i++){ String[] t = br.readLine().split(" "); int a = Integer.parseInt(t[0]); int b = Integer.parseInt(t[1]); int c = Integer.parseInt(t[2]); arr[a][b] = c; arr[b][a] = c; } //输入起点,终点 String[] last = br.readLine().split(" "); int start = Integer.parseInt(last[0]); int end = Integer.parseInt(last[1]); dis[start] = 0; for(int i = 1;i <= n;i++){ int minx = Integer.MAX_VALUE; int minmark = 1;; for(int j = 1;j <= n;j++){ if(vis[j] == false && dis[j] <= minx){ minx = dis[j]; minmark = j; } } vis[minmark] = true; for(int j =1;j<=n;j++){ if(vis[j]==false && arr[minmark][j] != Integer.MAX_VALUE &&dis[j]>dis[minmark]+arr[minmark][j]) dis[j]=dis[minmark]+arr[minmark][j]; } } System.out.println(dis[n]); } }
DFS
static int min = Integer.MAX_VALUE; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ String[] arr1 = line.split(" "); int n = Integer.parseInt(arr1[0]); int m = Integer.parseInt(arr1[1]); int[][] arr = new int[n+1][n+1]; boolean[] flag = new boolean[n+1]; for(int i = 0;i < n+1;i++){ for(int j = 0;j < n+1;j++){ arr[i][j] = Integer.MAX_VALUE; } } for(int i = 0;i < m;i++){ String[] t = br.readLine().split(" "); int a = Integer.parseInt(t[0]); int b = Integer.parseInt(t[1]); int c = Integer.parseInt(t[2]); arr[a][b] = c; arr[b][a] = c; } String[] last = br.readLine().split(" "); int start = Integer.parseInt(last[0]); int end = Integer.parseInt(last[1]); flag[start] = true; fincycle(arr, start, end, 0,flag,n); System.out.println(min); } } static void fincycle(int[][] arr,int s,int e,int cnt,boolean[] flag,int n){ if(cnt > min){ return; } if(s == e){ if(cnt < min){ min = cnt; } return; } for(int i = 1;i <= n;i++){ if(arr[s][i] != Integer.MAX_VALUE && flag[i] == false){ flag[i] = true; fincycle(arr, i, e, cnt+arr[s][i],flag,n); flag[i] = false; } } }