QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91902#5102. Dungeon CrawlerArefAAATL 218ms60212kbJava1110.7kb2023-03-29 20:56:562023-03-29 20:56:59

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 20:56:59]
  • 评测
  • 测评结果:TL
  • 用时:218ms
  • 内存:60212kb
  • [2023-03-29 20:56:56]
  • 提交

answer

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;

/**
 *
 * @author HP
 */
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;nodeArr[i].sDist=0;nodeArr[i].isKP=false;nodeArr[i].isTP=false;}
        
            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 a=g.sDistBFS();
                //System.out.println("sdist: "+a);
                int sol2=sumOfEdges+a;
                System.out.println(Math.min(sol2, sol1));
           }
            
        
    }}
    }

class Graph {
    int size;
    GraphNode start,hKey,trap,fP;
    public Graph(GraphNode s,GraphNode k,GraphNode t,int size){
    start=s;
    hKey=k;
    trap=t;
    this.size=size;
    this.BFS();
    fP=this.pOfK();
    }
     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;
        for (int i = 0; i < s.adjList.size(); i++) {
            if(s.adjList.get(i).n.isKP&&!s.adjList.get(i).n.isTP)visited[s.adjList.get(i).n.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]&&(!n.isKP||n.isTP)) {
                    visited[n.NodeNum-1] = true;
                    if(n.dist>maxFromNonKey)maxFromNonKey=n.dist;
                    queue.add(n);
                }
            }
        }
        return maxFromNonKey;
    } 
    public int sDistBFS()
    {
        GraphNode s=fP;
        int ss=s.dist;
        //System.out.println("fp "+fP.NodeNum);
        // 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);
        for (int i = 0; i < s.adjList.size(); i++) {
            if(!s.adjList.get(i).n.isKP||(s.adjList.get(i).n.isKP&&s.adjList.get(i).n.isTP))visited[s.adjList.get(i).n.NodeNum-1]=true;
        }
        int minSDist=999999999;
        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;
                //System.out.println("Before: Node: "+n.NodeNum+" dist: "+n.dist+" SDIST:"+ n.sDist+" Visited:"+visited[n.NodeNum-1]);
                if (!visited[n.NodeNum-1]&&!n.isKP) {
                    
                    visited[n.NodeNum-1] = true;
                    if(!n.parent.isKP){
                    n.sDist=n.parent.sDist-m.weight;}
                    else{n.sDist=n.parent.dist-m.weight;}
                    minSDist=Math.min(minSDist,n.sDist);
                    queue.add(n);
                }
                else if(!visited[n.NodeNum-1]){
                     visited[n.NodeNum-1] = true;
                     queue.add(n);
                 }
                //System.out.println("Before: Node: "+n.NodeNum+" dist: "+n.dist+" SDIST:"+ n.sDist+" Visited:"+visited[n.NodeNum-1]);
              
            }
        }
        //System.out.println("ss is:"+ss+" , mindist is:"+minSDist);
        return minSDist-2*ss;
    } 
    GraphNode pOfK(){
        GraphNode k=hKey;
        hKey.isKP=true;
        while(k.parent!=null){
            k=k.parent;
            k.isKP=true; }
        GraphNode t=trap;
        trap.isTP=true;
        while(t.parent!=null){
            t=t.parent;
            t.isTP=true; }
        GraphNode k1=hKey;
        GraphNode kt=hKey;
        boolean stch=true;
        while(k1!=null){
            
            if(k1.isTP){if(stch){kt=k1;stch=false;}
            }
            
            k1=k1.parent;
            
             }
        return kt;
        
    }
     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=999999999;
    boolean isKP=false;
    boolean isTP=false;
    int sDist=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;
    }
}
    

详细

Test #1:

score: 100
Accepted
time: 115ms
memory: 52656kb

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:

316
293
293
impossible
314

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 218ms
memory: 60212kb

input:

100 100
1 2 289384
2 3 930887
2 4 692778
4 5 636916
4 6 747794
4 7 238336
4 8 885387
8 9 760493
8 10 516650
8 11 641422
8 12 202363
8 13 490028
8 14 368691
8 15 520060
8 16 897764
16 17 513927
16 18 180541
16 19 383427
16 20 89173
16 21 455737
16 22 5212
16 23 595369
16 24 702568
16 25 956430
16 26 ...

output:

103526917
103484292
106288816
104379596
104405611
104775512
105434682
105291604
103838430
105371370
104677980
104175650
105894571
104509242
103971939
105376499
105223283
104153426
105082245
105413188
104130613
104800548
106846555
104138329
103769253
105456754
104044745
104385328
106973740
105460460
...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 122ms
memory: 53816kb

input:

10 6
1 2 4
2 3 7
2 4 8
4 5 6
4 6 4
4 7 6
4 8 7
8 9 3
8 10 10
3 8 1
10 4 7
1 7 3
7 2 9
8 10 3
4 1 6

output:

99
78
97
87
88
93

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 116ms
memory: 54136kb

input:

10 9
9 2 5
9 1 6
9 4 97
9 7 2
9 8 42
9 10 11
9 6 77
9 3 14
9 5 9
4 7 10
7 3 8
8 7 9
1 4 8
10 7 4
7 1 2
10 1 5
10 7 2
8 4 10

output:

352
427
impossible
443
418
427
418
418
407

result:

ok 9 lines

Test #5:

score: 0
Accepted
time: 99ms
memory: 56232kb

input:

9 9
2 3 48
9 5 31
7 3 97
4 3 16
1 7 24
5 3 82
8 2 51
6 4 33
1 2 8
3 6 8
1 6 3
9 5 6
2 6 4
5 6 1
9 6 4
2 8 9
4 9 2

output:

530
643
impossible
530
impossible
561
impossible
595
627

result:

ok 9 lines

Test #6:

score: 0
Accepted
time: 100ms
memory: 52740kb

input:

8 9
1 7 51
7 6 86
2 3 62
8 4 72
5 6 17
4 1 75
3 1 41
2 3 7
5 8 4
6 1 3
8 6 2
4 2 7
8 5 6
2 1 5
7 1 6
6 7 8

output:

551
impossible
524
558
579
impossible
551
705
524

result:

ok 9 lines

Test #7:

score: 0
Accepted
time: 130ms
memory: 54072kb

input:

9 9
5 4 13
9 2 10
1 9 25
7 6 34
4 2 77
3 8 67
8 1 57
6 9 100
6 4 1
4 1 7
3 2 9
4 9 7
7 9 3
6 2 1
2 8 4
8 6 2
6 5 9

output:

517
545
impossible
530
483
517
642
584
impossible

result:

ok 9 lines

Test #8:

score: 0
Accepted
time: 90ms
memory: 53680kb

input:

10 10
2 4 26
9 8 39
4 5 88
6 3 70
7 6 7
10 4 41
8 3 57
1 6 15
5 6 9
2 8 6
3 9 1
5 7 8
4 7 8
7 6 4
2 7 3
6 8 2
5 4 10
4 8 9
1 5 9

output:

impossible
496
529
441
531
415
566
529
441
523

result:

ok 10 lines

Test #9:

score: 0
Accepted
time: 127ms
memory: 50424kb

input:

10 9
3 2 6
2 1 18
8 1 44
1 9 42
6 3 72
10 8 46
7 10 93
5 3 11
4 10 13
7 3 1
8 2 5
7 5 4
5 10 8
3 1 4
6 4 3
10 1 6
5 10 8
2 10 4

output:

impossible
550
584
impossible
483
impossible
504
impossible
489

result:

ok 9 lines

Test #10:

score: -100
Time Limit Exceeded

input:

2000 199998
126 244 481188299
718 1159 740107180
1327 1250 248943862
977 1092 780169400
826 27 932696654
1668 638 478193038
229 174 176675890
1251 646 843918836
102 1973 593920932
236 218 165399894
760 151 890198591
232 502 10739184
1961 1409 45917915
548 1840 974742709
1096 630 280975617
1110 1048 ...

output:

460286122
impossible
458590962
457433555
457270452
impossible
462949634
458737618
459362375
459376917
impossible
impossible
471834165
impossible
impossible
impossible
456848198
461352945
459457051
461516000
457063539
460380279
impossible
459686542
impossible
458793209
457491809
457219644
impossible
...

result: