글 읽기 - 반례를..모르겠습니다

anwlro0212 3년 전 0

33 퍼에서 멈춥니다..

다익스트라로 최단경로 구하고

그 경로를 저장한 후에

그 경로와 g,h 를 비교해서 맞으면 추가하는 방식인데 반례가 뭘까요?

import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
	int node;
	int cost;
	Node(int node,int cost){
		this.node=node;
		this.cost=cost;
	}
	@Override
	public int compareTo(Node o) {
		if(this.cost>o.cost)
			return 1;
		return -1;
	}
}
public class Main{
	static ArrayList<Node> graph[];

	static int number[];
	public static void main(String args[])throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		int count=Integer.parseInt(br.readLine());
		for(int v=0;v<count;v++) {
			st=new StringTokenizer(br.readLine());
			int n=Integer.parseInt(st.nextToken());
			int m=Integer.parseInt(st.nextToken());
			int t=Integer.parseInt(st.nextToken());
			st=new StringTokenizer(br.readLine());
			int s=Integer.parseInt(st.nextToken());
			int g=Integer.parseInt(st.nextToken());
			int h=Integer.parseInt(st.nextToken());

			number=new int[n+1];
			graph=new ArrayList[n+1];
			for(int i=1;i<graph.length;i++) {
				graph[i]=new ArrayList<>();
			}
			for(int i=0;i<m;i++) {
				st=new StringTokenizer(br.readLine());
				int a=Integer.parseInt(st.nextToken());
				int b=Integer.parseInt(st.nextToken());
				int c=Integer.parseInt(st.nextToken());
				graph[a].add(new Node(b,c));
				graph[b].add(new Node(a,c));
			}
			ArrayList<Integer> f=new ArrayList<>();

			dijkstra(s,graph.length);

			
			for(int i=0;i<t;i++) {
				Stack<Integer> stack=new Stack<>();
				ArrayList<Integer> list=new ArrayList<>();
				int temp= Integer.parseInt(br.readLine());
				int temp2=temp;
				stack.push(temp);
				while(number[temp]!=0) {
					stack.push(number[temp]);
					temp=number[temp];
				}
				while(!stack.isEmpty())
					list.add(stack.pop());

				if(list.size()<2) {
					continue;
				}

				for(int j=0;j<list.size()-1;j++) {
					if(list.get(j)==g&&list.get(j+1)==h) {
						f.add(temp2);
						break;
					}
					else if(list.get(j)==h&&list.get(j+1)==g) {
						f.add(temp2);
						break;
					}
				}
			}
			
			Collections.sort(f);
			for(int i=0;i<f.size();i++) {
				sb.append(f.get(i)+" ");
			}
			sb.append("\n");

		}
		System.out.println(sb);



	}
	public static void dijkstra(int start, int length) {

		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.add(new Node(start,0));
		boolean visited[]=new boolean[length];
		int dist[]=new int[length];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start]=0;

		while(!pq.isEmpty()) {
			int nowVertex=pq.poll().node;
			if(visited[nowVertex]==true)
				continue;
			visited[nowVertex]=true;
			for(Node next:graph[nowVertex]) {
				if(dist[next.node]>dist[nowVertex]+next.cost) {
					number[next.node]=nowVertex;
					dist[next.node]=dist[nowVertex]+next.cost;
					pq.add(new Node(next.node,dist[next.node]));
				}
			}
		}

		
	}
}

psj_0708 3년 전 12

최단 경로가 여러 개가 나오는 경우 g,h를 지나는 최단경로가 존재하더라도 dijkstra에서 그걸 놓칠 수 있습니다.

아래 반례를 생각해 보시면 도움이 될 것 같네요.

input
1
5 5 2
1 2 3
1 4 3
4 5 3
1 2 2
2 3 2
3 5 2
3
5

output: 3
answer: 3 5

anwlro0212 3년 전 4

와 감사합니다!! 11779번 문제는 최단경로가 여러개여도 정답으로 인정해줘서

(그 문제 예제출력이

4
3
1 3 5

인데

1 4 5 출력해도 정답이 됐었씁니다. 이문제도 같은 맥락일 줄 알았는데 아니였네요!!

우선 제가 알고리즘을 이상하게 짜진 않았다는 것에 다행..(휴..ㅎㅎ)

참고해서 중복경로일땐 어떻게 해야하나 생각해보겠습니다 오늘은 늦어서 일어나면 일어나자마자 풀어볼게요~

진짜 감사해요 좋은하루 보내세요!!

anwlro0212 3년 전 4

시간이 지나서 보실까는 모르겠습니다만 문제 덕분에 풀었습니다 ..!

제가 알고리즘을 잘못 짠게 결국 맞았군요 ㅋㅋㅋ

중간에 들러야 하는 경로 g까지의 최단거리를 구하고, 또 g에서 h 까지의 거리, h에서 목적지 까지의 거리를 각각 구해주고 더해줘서

s에서 목적지까지의 거리와 같은지 비교해봤습니다 ! 경로 되추적은 하지 않아도 되는군요

문제 못풀어서 찝찝할 뻔했는데 다시 한 번 감사합니다

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

문제

문제

출처

ICPC

반례를..모르겠습니다

anwlro0212 3년 전 0

psj_0708 3년 전 12

anwlro0212 3년 전 4

anwlro0212 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말