QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #91898 | #5102. Dungeon Crawler | ArefAAA | WA | 173ms | 59076kb | Java11 | 10.7kb | 2023-03-29 20:54:58 | 2023-03-29 20:55:00 |
Judging History
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: 0
Wrong Answer
time: 173ms
memory: 59076kb
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:
fp 1 ss is:0 , mindist is:1 sdist: 1 316 fp 1 ss is:0 , mindist is:-9 sdist: -9 293 293 impossible fp 1 ss is:7 , mindist is:20 sdist: 6 314
result:
wrong answer 1st lines differ - expected: '316', found: 'fp 1'