QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91556#5102. Dungeon CrawlerArefAAAWA 99ms56012kbJava117.5kb2023-03-29 05:52:472023-03-29 05:52:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 05:52:51]
  • 评测
  • 测评结果:WA
  • 用时:99ms
  • 内存:56012kb
  • [2023-03-29 05:52:47]
  • 提交

answer

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
public class CodeJamDungion {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner s=new Scanner(System.in);
        int gSize=s.nextInt();
        int sSize=s.nextInt();
        GraphNode[] nodeArr=new GraphNode[gSize+1];
        for (int i = 1; i < gSize+1; i++) {
            nodeArr[i]=new GraphNode(i);
        }
        for (int i = 1; i < gSize; i++) {
            int sNode=s.nextInt();
            
            int eNode=s.nextInt();
           
            int weight=s.nextInt();
            
            nodeArr[sNode].adjList.add(new Pair(nodeArr[eNode],weight));
            nodeArr[eNode].adjList.add(new Pair(nodeArr[sNode],weight));
        }
        
            
        for (int m = 0; m < sSize; m++) {
            
        
        
            for (int i = 1; i < nodeArr.length; i++) {nodeArr[i].parent=null;nodeArr[i].dist=0;}
        
            int start=s.nextInt();
            int key=s.nextInt();
            int trap=s.nextInt();
            Graph g=new Graph(nodeArr[start],nodeArr[key],nodeArr[trap],gSize);
            if(g.isImpossible())System.out.println("impossible");
            else if(g.isEasy()){
                int sumOfEdges=0;
                int max=0;
                for (int i = 1; i < nodeArr.length; i++) {
                
                    for (int j = 0; j < nodeArr[i].adjList.size(); j++) {
                        sumOfEdges+=nodeArr[i].adjList.get(j).weight;
                    }
                }
                for (int i = 1; i < nodeArr.length; i++) {
                    if(nodeArr[i].dist>max)max=nodeArr[i].dist;
                }
                System.out.println(sumOfEdges-max);
            }
            else {
                int maxN=g.NKBFS();
                int sol1=0;
                int sumOfEdges=0;
                for (int i = 1; i < nodeArr.length; i++) {
                
                    for (int j = 0; j < nodeArr[i].adjList.size(); j++) {
                        sumOfEdges+=nodeArr[i].adjList.get(j).weight;
                    }
                }
                sol1=sumOfEdges-maxN;
                int sol2=sumOfEdges-g.KBFS()+nodeArr[key].dist*2;
                System.out.println(Math.min(sol2, sol1));
           }
            
        
    }}
    }

class Graph {
    int size;
    GraphNode start,hKey,trap;
    public Graph(GraphNode s,GraphNode k,GraphNode t,int size){
    start=s;
    hKey=k;
    trap=t;
    this.size=size;
    this.BFS();
    }
     public void clear(){
         
     }
    public void BFS()
    {
        GraphNode s=start;
        s.dist=0;
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[size];
 
        // Create a queue for BFS
        LinkedList<GraphNode> queue
            = new LinkedList<GraphNode>();
 
        // Mark the current node as visited and enqueue it
        visited[s.NodeNum-1] = true;
        queue.add(s);
 
        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            
 
            // Get all adjacent vertices of the dequeued
            // vertex s If a adjacent has not been visited,
            // then mark it visited and enqueue it
            ListIterator<Pair> i = s.adjList.listIterator();
            while (i.hasNext()) {
                Pair m = i.next();
                GraphNode n=m.n;
                
                if (!visited[n.NodeNum-1]) {
                    visited[n.NodeNum-1] = true;
                    n.parent=s;
                    n.dist=s.dist+m.weight;
                    queue.add(n);
                }
            }
        }
    } 
    public int KBFS()
    {
        GraphNode s=hKey;
        
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[size];
 
        // Create a queue for BFS
        LinkedList<GraphNode> queue
            = new LinkedList<GraphNode>();
 
        // Mark the current node as visited and enqueue it
        visited[s.NodeNum-1] = true;
        visited[s.parent.NodeNum-1]=true;
        queue.add(s);
        int maxFromKey=s.dist;
        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            
 
            // Get all adjacent vertices of the dequeued
            // vertex s If a adjacent has not been visited,
            // then mark it visited and enqueue it
            ListIterator<Pair> i = s.adjList.listIterator();
            while (i.hasNext()) {
                Pair m = i.next();
                GraphNode n=m.n;
                
                if (!visited[n.NodeNum-1]) {
                    visited[n.NodeNum-1] = true;
                    if(n.dist>maxFromKey)maxFromKey=n.dist;
                    queue.add(n);
                }
            }
        }
        return maxFromKey;
    } 
    public int NKBFS()
    {
        GraphNode s=start;
        
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[size];
 
        // Create a queue for BFS
        LinkedList<GraphNode> queue
            = new LinkedList<GraphNode>();
 
        // Mark the current node as visited and enqueue it
        visited[s.NodeNum-1] = true;
        visited[hKey.NodeNum-1]=true;
        queue.add(s);
        int maxFromNonKey=s.dist;
        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            
 
            // Get all adjacent vertices of the dequeued
            // vertex s If a adjacent has not been visited,
            // then mark it visited and enqueue it
            ListIterator<Pair> i = s.adjList.listIterator();
            while (i.hasNext()) {
                Pair m = i.next();
                GraphNode n=m.n;
                
                if (!visited[n.NodeNum-1]) {
                    visited[n.NodeNum-1] = true;
                    if(n.dist>maxFromNonKey)maxFromNonKey=n.dist;
                    queue.add(n);
                }
            }
        }
        return maxFromNonKey;
    } 
     boolean isImpossible(){
         GraphNode s=start;
         GraphNode k=hKey;
         GraphNode t=trap;
        
         boolean Impossible=false;
         GraphNode n=k.parent;
         while(n!=null){
             if(n==t)Impossible=true;
             n=n.parent;
         }
         return Impossible;
     }
     boolean isEasy(){
         GraphNode s=start;
         GraphNode k=hKey;
         GraphNode t=trap;
         
         boolean Easy=false;
         GraphNode n=t.parent;
         while(n!=null){
             if(n==k)Easy=true;
             n=n.parent;
         }
         return Easy;
     }
     
}
class GraphNode {
    int NodeNum;
    ArrayList<Pair> adjList;
    GraphNode parent=null;
    int dist=0;
    public GraphNode(int num){
    NodeNum=num;
    adjList=new ArrayList<Pair>();
    }
    
}
class Pair{
    GraphNode n;
    Integer weight;
    public Pair(GraphNode n,Integer weight){
        this.n=n;
        this.weight=weight;
    }
}
    

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 99ms
memory: 56012kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

293
293
293
impossible
294

result:

wrong answer 1st lines differ - expected: '316', found: '293'