[数据结构与算法]【蓝桥杯day2】

题目1

题目描述

?解题代码：

import java.util.Scanner;
import java.util.*;

// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    private static final Scanner in = new Scanner(System.in);
    // private static List<int[]> edges =new ArrayList<>();
    private static List<int[]> edges = new ArrayList<>();

    public static void main(String[] args) {
        
        //在此输入您的代码...
    
        add('A','C',1);
        add('A','D',1);
        add('A','E',1);
        add('B','G',1);
        add('D','E',1);
        add('D','H',1);
        add('E','H',1);
        add('F','G',1);
        add('F','J',1);
        add('H','I',1);
        add('K','N',1);
        add('L','M',1);
        add('L','R',1);
        add('M','Q',1);
        add('M','S',1);
        add('N','P',1);
        add('O','P',1);
        add('O','Q',1);
        add('R','S',1);
        add('A','B',2);
        add('B','J',2);
        add('D','G',2);
        add('D','I',2);
        add('G','K',2);
        add('H','L',2);
        add('J','S',2);
        add('K','P',2);
        add('M','N',2);
        add('C','D',3);
        add('C','F',3);
        add('C','G',3);
        add('E','I',3);
        add('G','I',3);
        add('I','M',3);
        add('K','L',3);
        add('O','R',3);
int[] dist=new int[128];//asicc码值只有128个用来统计字符出现的次数
Arrays.fill(dist,Integer.MAX_VALUE>>1);
dist['A']=0;
int n=edges.size();
for(int i=0;i<n-1;i++){
  for(int[] edge:edges){
    int u=edge[0],v=edge[1],w=edge[2];
    dist[v]=Math.min(dist[v],dist[u]+w);
  }
}
System.out.println(dist['S']);

      
        
    }
      private static void add(char u,char v,int w){
          edges.add(new int[]{u,v,w});
          edges.add(new int[]{v,u,w});
        }
}

java语法复习：

1.static

?2.ArrayList求长度的方法为size(),添加元素的方法为add().

3.Arrays.fill(数组名，填充值)数组填充的方法，这里填充的是Interger.MAX_VALUE>>1，因为要加上边值，避免溢出。

算法思想：

第一次遇上最短路径问题，这个方法是Bellman–Ford?算法，其主要思想就是松弛，循环n-1次（n为点数）每次松弛找出除出发点以外的其他点离出发点的最短距离，更新n-1次得到所有点离出发点的最短距离。