QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #91555 | #5102. Dungeon Crawler | ArefAAA | Compile Error | / | / | Java11 | 7.4kb | 2023-03-29 05:51:56 | 2023-03-29 05:51:57 |
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:51:57]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-03-29 05:51:56]
- 提交
answer
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
CodeJamDungion.java:231: error: cannot find symbol
ArrayList<Pair> adjList;
^
symbol: class ArrayList
location: class GraphNode
CodeJamDungion.java:9: error: cannot find symbol
Scanner s=new Scanner(System.in);
^
symbol: class Scanner
location: class CodeJamDungion
CodeJamDungion.java:9: error: cannot find symbol
Scanner s=new Scanner(System.in);
^
symbol: class Scanner
location: class CodeJamDungion
CodeJamDungion.java:94: error: cannot find symbol
LinkedList<GraphNode> queue
^
symbol: class LinkedList
location: class Graph
CodeJamDungion.java:95: error: cannot find symbol
= new LinkedList<GraphNode>();
^
symbol: class LinkedList
location: class Graph
CodeJamDungion.java:109: error: cannot find symbol
ListIterator<Pair> i = s.adjList.listIterator();
^
symbol: class ListIterator
location: class Graph
CodeJamDungion.java:132: error: cannot find symbol
LinkedList<GraphNode> queue
^
symbol: class LinkedList
location: class Graph
CodeJamDungion.java:133: error: cannot find symbol
= new LinkedList<GraphNode>();
^
symbol: class LinkedList
location: class Graph
CodeJamDungion.java:148: error: cannot find symbol
ListIterator<Pair> i = s.adjList.listIterator();
^
symbol: class ListIterator
location: class Graph
CodeJamDungion.java:171: error: cannot find symbol
LinkedList<GraphNode> queue
^
symbol: class LinkedList
location: class Graph
CodeJamDungion.java:172: error: cannot find symbol
= new LinkedList<GraphNode>();
^
symbol: class LinkedList
location: class Graph
CodeJamDungion.java:187: error: cannot find symbol
ListIterator<Pair> i = s.adjList.listIterator();
^
symbol: class ListIterator
location: class Graph
CodeJamDungion.java:236: error: cannot find symbol
adjList=new ArrayList<Pair>();
^
symbol: class ArrayList
location: class GraphNode
13 errors