赞
踩
思路:看了一下蓝不过海呀的视频,要找到入度为0的点,删掉该点和该点的出度,要用一个数据结构存起来边,而且要方便删除
- import java.util.*;
-
- class Main{
- public static int n;
- public static int m;
- public static void main(String[] args){
- Scanner scanner = new Scanner(System.in);
- n = scanner.nextInt();
- m = scanner.nextInt();
- int[][] grid = new int[m][2];
- for(int i=0; i<m; i++){
- int s = scanner.nextInt();
- int t = scanner.nextInt();
- grid[i] =
- }
-
- for(){
- //遍历map,从1-5,找不到的value,说明入度为0
-
- //删掉该点和该点的出度
-
- //将该点加入到结果数组中
-
- }
-
- // 遍历输出数组
- }
- }
- import java.util.*;
- class Main{
- public static void main(String[] args){
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- int m = sc.nextInt();
- int[] in_degree = new int[n];
- Map<Integer, ArrayList<Integer>> map = new HashMap<>();
- ArrayList<Integer> res= new ArrayList<>();
-
- for(int i=0;i<m;i++){
- int s = sc.nextInt();
- int t = sc.nextInt();
- in_degree[t] ++;
- ArrayList<Integer> list = new ArrayList<>();
- if (!map.containsKey(s)){
- list.add(t);
- }else{
- list = map.get(s);
- list.add(t);
- }
- map.put(s, list);
- }
-
- Queue<Integer> queue = new LinkedList<>();
- for(int i =0;i<n;i++){
- if(in_degree[i] == 0) queue.offer(i);
- }
-
- while (!queue.isEmpty()){
- int cur = queue.peek();
- queue.poll();
- res.add(cur);
- if(map.containsKey(cur)){
- ArrayList<Integer> files = map.get(cur);
- if(!files.isEmpty()){
- for(int i = 0;i<files.size();i++){
- in_degree[files.get(i)]--;
- if (in_degree[files.get(i)]==0) queue.offer(files.get(i));
- }
- }
-
- }
-
- }
-
- if(res.size() == n){
- for (int i = 0;i<n-1;i++){
- System.out.print(res.get(i) + " ");
- }
- System.out.print(res.get(res.size()-1) );
- }else{
- System.out.print(-1);
- }
-
- }
- }
Map<Integer, ArrayList<Integer>> map = new HashMap<>();存储节点和节点依赖关系
题目:47. 参加科学大会(第六期模拟笔试) (kamacoder.com)
思路:直接看的蓝不过海呀的视频,懒得自己写了,抄一遍
- import java.util.*;
-
- public class Main {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
-
- int n = scanner.nextInt(); // 顶点数
- int m = scanner.nextInt(); // 边数
-
- int[][] grid = new int[n + 1][n + 1];
- for (int i = 1; i <= n; i++) {
- Arrays.fill(grid[i], Integer.MAX_VALUE);
- }
-
- for (int i = 0; i < m; i++) {
- int p1 = scanner.nextInt();
- int p2 = scanner.nextInt();
- int val = scanner.nextInt();
- grid[p1][p2] = val;
- }
-
- int start = 1;
- int end = n;
-
- // 存储从源点到每个节点的最短距离
- int[] minDist = new int[n + 1];
- Arrays.fill(minDist, Integer.MAX_VALUE);
-
- // 记录顶点是否被访问过
- boolean[] visited = new boolean[n + 1];
-
- minDist[start] = 0; // 起始点到自身的距离为0
-
- for (int i = 1; i <= n; i++) { // 遍历所有节点
- int minVal = Integer.MAX_VALUE;
- int cur = 1;
-
- // 1、选距离源点最近且未访问过的节点
- for (int v = 1; v <= n; ++v) {
- if (!visited[v] && minDist[v] < minVal) {
- minVal = minDist[v];
- cur = v;
- }
- }
-
- visited[cur] = true; // 2、标记该节点已被访问
-
- // 3、第三步,更新非访问节点到源点的距离(即更新minDist数组)
- for (int v = 1; v <= n; v++) {
- if (!visited[v] && grid[cur][v] != Integer.MAX_VALUE && minDist[cur] + grid[cur][v] < minDist[v]) {
- minDist[v] = minDist[cur] + grid[cur][v];
- }
- }
- }
-
- if (minDist[end] == Integer.MAX_VALUE) {
- System.out.println(-1); // 不能到达终点
- } else {
- System.out.println(minDist[end]); // 到达终点最短路径
- }
-
- scanner.close();
- }
- }
dijkstra三部曲:
minDist数组 用来记录 每一个节点距离源点的最小距离
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。