dij算法

刚做了蓝桥杯上的《星际旅行》,用到了迪克斯算法，每两个相连的星球可以互相到达，相当于无向图（双向可达），给出初始位置和definition，判断最多能到达的星球的期望，既然是要求最多，那肯定两个星球间的距离要最小，那么就要用到迪克斯算法（从图中每次选与选定点相邻的点（邻居点），且没有走过的点，通过选定的点为基础更新邻居点的最小值），需要用到首先是记录无向图的数组g[]，记录两点间最短距离的数组dis[i][j](表示i到j之间的最短距离）,以及vis[]进行对点是否处理过的标记，用priority_queue队列实现每次都取出最近的点，遍历最近点的邻居点再放到队列离去，这样就能遍历完整张图了。照我的理解是通过给定的起点，通过邻居往外拓展，从下向上更新两点间最小距离，这也算预处理了把，最后再查表输出。