BOJ 1848 동굴 탐험

문제 

https://www.acmicpc.net/problem/1848

1번 동굴에서 시작해서 동굴을 탐색하고, 다시 1번으로 나오는 최단거리를 찾는 문제..

조건은 다음과 같다.

대회의 목표는 시작방에서 출발하여 동굴 내부를 달려, 다시 시작방으로 되돌아 와 빠져 나오는 것인데, 그 경로는 참가자가 마음대로 정할 수 있지만 두 가지 조건을 지켜야 한다. 

 첫째 조건은, 시작방 이외의 방을 최소한 하나는 거쳐야 한다는 것이며, 

 둘째 조건은, 어떤 방과 터널도 최대 한 번밖에 방문할 수 없다는 것이다. 

 (시작방은 물론 두 번 방문하게 되므로 예외이다.)

첫째 줄에 n과 m이 주어진다. (3≤n≤5000, 3≤m≤10000) 이는 각각 동굴 내부의 방의 개수와, 터널의 개수를 나타낸다.

  이어지는 m개의 줄에는 각각 터널의 정보를 제공하는 네 개의 숫자 a, b, c, d가 포함되어 있다. 이것은 a번 방에서 b번 방으로 갈 때는 c의 시간이 걸리고, 반대로 b번 방에서 a번 방으로 갈 때는 d의 시간이 걸린다는 의미이다. (1≤a, b≤n. a≠b. 1≤c, d≤10000)

  방의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 방이 시작방이다. 언제나 조건을 만족하는 경로가 하나는 있다고 가정해도 좋다.

샘플 예제에서는 

3 3
1 2 4 3
2 3 4 2
1 3 1 1

답이 6 이다.

즉 1 -> 2 -> 3 -> 1 로 나와야 한다.

문제의 조건대로라면 1->3->1 로 나오면 2로 최소가 된다. 하지만 이건 답이 아니다.

모든 방을 탐색하는 조건으로 하면 답이 틀리다고 나온다.

아~~ 뭐가 틀린거지?

계속 3번째 테스트 케이스에서 틀리다고 나온다..ㅠㅠ 된장

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer; public class boj1848 { static int N, M; static long[] D; static List<Node>[] route; static class Node implements Comparable<Node> { int e; long v; String visit = "1"; int vcnt = 0; public Node(int e, int v) { this.e = e; this.v = v; } public Node(int e, long v, String visit, int vcnt) { this.e = e; this.v = v; this.visit = visit; this.vcnt = vcnt; } public int getVcnt(){ return vcnt; } public String getVisit() { return visit; } public boolean isVisited(int e){ int idx = visit.indexOf(""+e); if(idx > -1) return true; else return false; } @Override public int compareTo(Node o) { return Long.compare(this.v, o.v); } @Override public String toString() { getVcnt(); return "Node [e=" + e + ", v=" + v + ", visit=" + visit + ", vcnt=" + vcnt + "]"; } } public static void main(String[] args) throws IOException { System.setIn(new FileInputStream("res/input1848.txt")); // System.setIn(new FileInputStream("res/out.txt")); long Start = System.currentTimeMillis(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.nextToken());  // number of room M = Integer.parseInt(st.nextToken());  // number of cave route = new List[N+1]; D = new long[N+1]; int a, b, c, d; for (int i = 1; i < M+1; i++) { st = new StringTokenizer(br.readLine(), " "); a = Integer.parseInt(st.nextToken()); b = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); d = Integer.parseInt(st.nextToken()); if(route[a]==null) route[a] = new ArrayList<Node>(); if(route[b]==null) route[b] = new ArrayList<Node>(); route[a].add(new Node(b, c)); route[b].add(new Node(a, d)); } for (int i = 1; i < N+1; i++) { D[i] = Long.MAX_VALUE; } PriorityQueue<Node> pq = new PriorityQueue<Node>(); Node nd=null; pq.add(new Node(1, 0)); boolean start = false; long min = Long.MAX_VALUE; while (!pq.isEmpty()) { nd = pq.poll(); // System.out.println(nd); if(route[nd.e]==null) continue; if(nd.e==1){ // if(nd.getVcnt()==N) break; if(!start) start = true; else { if(nd.vcnt>2 && min>nd.v) min = nd.v; continue; } } for (Node node : route[nd.e]) { if(node.e==1){ // int size = nd.visit.split("1,").length; // if(size==2) pq.add(new Node(node.e, node.v + nd.v,nd.visit+","+node.e, nd.vcnt+1)); } else if(!nd.isVisited(node.e)) if(D[node.e]>node.v + nd.v) { D[node.e]=node.v + nd.v; pq.add(new Node(node.e, D[node.e],nd.visit+","+node.e, nd.vcnt+1)); } } } // System.out.println(nd.v); System.out.println(min); System.out.println("Total : " + (System.currentTimeMillis()-Start)+" ms"); } }