QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91556 | #5102. Dungeon Crawler | ArefAAA | WA | 99ms | 56012kb | Java11 | 7.5kb | 2023-03-29 05:52:47 | 2023-03-29 05:52:51 |
Judging History
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'