글 읽기 - 이 코드는 왜 답이 아닐까요?

gkdud583 3년 전 0

거쳐야 하는 두 정점이 u1,u2이라고 할때 모든 정점을 최대한 u1,u2를 거치는 최단거리로 갱신하고

마지막 정점에서 u1,u2거치지 않으면 -1을 출력하도록 했습니다.

이 방법이 애초에 답이 될수 없는건가요 아니면 코드에 문제가 있는걸까요?

import java.util.*;
import java.io.*;

public class hellojava{
   
    public static final int MAX = 2100000000;
    public static class node{
        int v;
        long dist;
        int condition1;
        int condition2;
        public node(int v,long dist,int condition1,int condition2){
            this.v = v;
            this.dist = dist;
            this.condition1 = condition1;
            this.condition2 = condition2;
        }
    }
    public static void main(String[]args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());
       
        int v = Integer.parseInt(stz.nextToken());
        int e = Integer.parseInt(stz.nextToken());
        
        PriorityQueue<node> heap = new PriorityQueue<node>(new Comparator<node>() {
            @Override
            public int compare(node o1, node o2) {
                if(o1.dist < o2.dist) return -1;
                else if(o1.dist == o2.dist) return 0;
                else return 1;
                
            } 
    
            
        });
      
    
        long dist[][] = new long[v+1][3]; // 0 | 1 | 2
        int check[] = new int[v+1];
        ArrayList<node>[] graph = new ArrayList[v + 1];
        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<node>();
        }
        
        
        for(int j=0; j<e; j++){
            stz = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(stz.nextToken());
            int n2 = Integer.parseInt(stz.nextToken());
            int w = Integer.parseInt(stz.nextToken());
            graph[n1].add(new node(n2, w,0,0));
            graph[n2].add(new node(n1, w,0,0));

         
            
        }
        
        stz = new StringTokenizer(br.readLine());
        int condition1 = Integer.parseInt(stz.nextToken());
        int condition2 = Integer.parseInt(stz.nextToken());
        for(int i=1; i<=v; i++){
            dist[i][0] = MAX;
            if(i == condition1)
                dist[i][1] = 1;
            else if(i == condition2)
                dist[i][2] = 1;
        }
        
        for(int i=1; i<=v; i++){
            for(int j=0,size=graph[i].size(); j<size; j++){
                if(graph[i].get(j).v == condition1){
                    graph[i].get(j).condition1 = 1;
                }
                else if(graph[i].get(j).v == condition2){
                    graph[i].get(j).condition2 = 1;
                }
            }
           
        }
        
        dist[1][0] = 0;
      
        heap.add(new node(1,dist[1][0],(int)dist[1][1],(int)dist[1][2])); 
        
        while(!heap.isEmpty()){
            node u = heap.poll();
           
            if(check[u.v] == 0){
                // System.out.println("pop:"+u.v+" "+u.dist+" "+u.condition1+" "+u.condition2);
                for(int i=0,size=graph[u.v].size(); i<size; i++){
                    node tmp = graph[u.v].get(i);
                    int c1 = (int)((u.condition1 + tmp.condition1) >= 2 ? 1 : u.condition1 + tmp.condition1);
                    int c2 = (int)((u.condition2 + tmp.condition2) >= 2 ? 1 : u.condition2 + tmp.condition2);
                    //기존 경로보다 u1,u2를 거치는 수가 클 경우 바꿔줌
                    if(dist[tmp.v][1] + dist[tmp.v][2] < c1 + c2){
                        dist[tmp.v][0] = u.dist + tmp.dist;
                        dist[tmp.v][1] = c1;
                        dist[tmp.v][2] = c2;
                        heap.add(new node(tmp.v,dist[tmp.v][0],(int)dist[tmp.v][1],(int)dist[tmp.v][2]));

                    }
                    //거치는 수가 같은 경우 새로운 경로의 합이 더 작으면 바꿔줌
                    else if(dist[tmp.v][1] + dist[tmp.v][2] == c1 + c2){
                        if(dist[tmp.v][0] > u.dist + tmp.dist){
                            dist[tmp.v][0] = u.dist + tmp.dist;
                            heap.add(new node(tmp.v,dist[tmp.v][0],(int)dist[tmp.v][1],(int)dist[tmp.v][2]));
                        }
                    }

                    // System.out.println("edge:" + tmp.v + " " +dist[tmp.v][0] + " " + dist[tmp.v][1] + " " +dist[tmp.v][2]);
                    //두 정점을 모두 거치는 해당 정점까지의 최단경로가 결정됨.
                    if(u.condition1 == 1 && u.condition2 == 1)
                        check[u.v] = 1;
                
                }
            }
           
        
        }
           

        
       

        if(dist[v][1] != 1 || dist[v][2] != 1){
            System.out.print(-1);
        }
        else   
            System.out.print(dist[v][0]);

    }
    
    
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 코드는 왜 답이 아닐까요?

gkdud583 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말