QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91557 | #5102. Dungeon Crawler | Serdahsufyan | Compile Error | / | / | Java11 | 7.7kb | 2023-03-29 06:12:49 | 2023-03-29 06:12:52 |
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 06:12:52]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-03-29 06:12:49]
- 提交
answer
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package codejamproblem;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
/**
*
* @author HP
*/
public class CodeJamProblem {
/**
* @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;
}
}
//
详细
Please don't specify the package.