DAY58拓扑排序

记得添加边的话
利用List<List>，对每个点都建立一个列表，里面存放它所指向的点

软件构建

其实就是一个判断是否存在环的问题
方法：依次去掉入度为0的点

    public static void main(String[] args) {Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();List<List<Integer>> adjList=new ArrayList<>();for(int i=0;i<n;i++)adjList.add(new ArrayList<>());int[]inDegree=new int[n];for(int i=0;i<m;i++){int a=in.nextInt();int b=in.nextInt();adjList.get(a).add(b);inDegree[b]++;}Queue<Integer> que=new LinkedList<>();for(int i=0;i<n;i++){if(inDegree[i]==0)que.add(i);}List<Integer> res=new ArrayList<>();while (!que.isEmpty()) {int cur=que.poll();res.add(cur);for(int node:adjList.get(cur)){inDegree[node]--;if(inDegree[node]==0){que.add(node);}}}if(res.size()==n){for(int i=0;i<res.size();i++){System.out.print(res.get(i));if(i<res.size()-1)System.out.print(" ");}}else{System.out.println(-1);}}

参加科学大会

选择一条花费时间最少的路线

    public static void main(String[] args) {Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();int[][]graph=new int[n+1][n+1];for(int i=0;i<=n;i++){Arrays.fill(graph[i],Integer.MAX_VALUE);}for(int i=0;i<m;i++){int a=in.nextInt();int b=in.nextInt();int val=in.nextInt();graph[a][b]=val;}int start=1;int end=n;int[]minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);boolean[]visit=new boolean[n+1];minDist[start]=0;for(int i=1;i<=n;i++){int min=Integer.MAX_VALUE;int cur=1;//选取距离原点近且未访问过的点for(int v=1;v<=n;v++){if(!visit[v]&&minDist[v]<min){min=minDist[v];cur=v;}}visit[cur]=true;//更新非访问节点到源点的距离for(int v=1;v<=n;v++){if(!visit[v]&&graph[cur][v]!=Integer.MAX_VALUE){minDist[v]=minDist[cur]+graph[cur][v];}}}if(minDist[end]==Integer.MAX_VALUE){System.out.println(-1);}else{System.out.println(minDist[end]);}}