Silver Cow Party java优先队列实现

本文主要是介绍Silver Cow Party java优先队列实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：Silver Cow Party

两次迪杰斯特拉即可。这次使用了优先队列。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        ArrayList<Edge>[] roadOut = new ArrayList[N+1];
        //ArrayList<Edge>[] roadBack = new ArrayList[N+1];
        for(int i =1;i<=M;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            if(roadOut[start] == null){
                roadOut[start] = new ArrayList<Edge>();
            }
           /* if(roadBack[end] == null){
                roadBack[end] = new ArrayList<Edge>();
            }*/
            roadOut[start].add(new Edge(end,weight));
            //roadBack[end].add(new Edge(start,weight));
        }
        int[] visited = new int[N+1];
        //go out search
        int[] goOutList = new int[N+1];
        for(int m=1;m<=N;m++){
            Arrays.fill(visited,100000000);
            visited[m]=0;
            PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
            Edge init = new Edge(m,0);
            pq.add(init);
            Edge pollEdge;
            int newDist;
            while(!pq.isEmpty()){
                pollEdge = pq.poll();
                for(Edge nextEdge:roadOut[pollEdge.end]){
                    newDist = visited[pollEdge.end]+nextEdge.weight;
                    if(newDist<visited[nextEdge.end]){
                        visited[nextEdge.end] = newDist;
                        pq.add(nextEdge);
                    }
                }
            }
            goOutList[m] = visited[X];
        }
        //return search
        int[] returnList = new int[N+1];
        visited = new int[N+1];
        for(int m = 1;m<=N;m++){
            Arrays.fill(visited,100000000);
            visited[X]=0;
            PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
            Edge init = new Edge(X,0);
            pq.add(init);
            Edge pollEdge;
            int newDist;
            while(!pq.isEmpty()){
                pollEdge = pq.poll();
                for(Edge nextEdge:roadOut[pollEdge.end]){
                    newDist = visited[pollEdge.end]+nextEdge.weight;
                    if(newDist<visited[nextEdge.end]){
                        visited[nextEdge.end] = newDist;
                        pq.add(nextEdge);
                    }
                }
            }
            returnList[m] = visited[m];
        }

        int max=0;
         for(int m = 1;m<=N;m++){
            max = Math.max(goOutList[m]+returnList[m],max);
        }
        System.out.println(max);
    }


    static class Edge implements Comparable<Edge>{
        int end;
        int weight;

        public Edge(){

        }
        public Edge(int end,int weight){
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight-o.weight;
        }
    }
}

这篇关于Silver Cow Party java优先队列实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！