글 읽기 - 50%에서 틀리는데 원인을 못 찾겠습니다

rhino333 7년 전 0

풀이 자체가 틀린건지 예외처리가 안된건지 모르겠네요.

다익스트라 여러 번 돌려서 최단경로가 아닌 값이 나올 때 까지 반복했습니다.

코드는 종만북 다익스트라 참고했구요, 간선을 지우는 대신 최단 경로에 속한 정점들을 표시해서

현재 정점과 다음 정점이 모두 최단경로에 속한 정점일 때 넘어가게 구현했습니다.

#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

using ii = pair<int,int>;
const int INF = 987654321;
int v,e, s, d;
vector<ii> adj[10001];
vector<int> parent(10001,-1);
vector<bool> isShort(10001,false);
priority_queue<ii> pq;

int dij2(){
	vector<int> dist(10001,INF);
	pq.push(make_pair(0,s));
	dist[s] = 0;
	parent[s] = s;

	while(!pq.empty()){
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if(dist[cur] < cost) continue;

		for(auto& there : adj[cur]){
			int next = there.first;
			int nextDist = cost + there.second;
            //현재,다음 정점이 이미 최단 경로로 판정됐다면 넘어간다
			if(isShort[cur] && isShort[next]) continue;
			if(isShort[next]) continue;
			if(dist[next] > nextDist){
				dist[next] = nextDist;
				pq.push(make_pair(-nextDist,next));
				parent[next] = cur;
			}
		}
	}
	int p = d;
    //목적지에 도달하지 못하면 parent[p] =-1이므로 무시한다
	if(parent[p]>=0){
		isShort[p] = true;
		while(parent[p] != p) {
			p = parent[p];
			isShort[p] = true;
		}
	}
	return dist[d];
}

int main(){
	while(scanf("%d %d",&v,&e)) {
		if(v==0 && e==0) break;
		scanf("%d %d",&s,&d);
		fill(parent.begin(),parent.end(),-1);
		fill(isShort.begin(),isShort.end(),false);
		for(int i=0; i<10001; ++i) adj[i].clear();
		for(int i=0; i<e; ++i){
			int a,b,c;scanf("%d %d %d",&a,&b,&c);
			adj[a].push_back(make_pair(b,c));
		}
		int ret1 = dij2();
		int ret2 = dij2();
        //최단경로와 같지 않은 값이 나올 때 까지 반복
		while(1){
			if(ret2 == INF){
				puts("-1");
				break;
			}else if(ret1 != ret2) {
				printf("%d\n",ret2);
				break;
			} 
			ret2 = dij2();
		}	
	}
}

ntopia 7년 전 1

isShort[cur] == true 이고 isShort[next] == true 이지만

cur 에서 next 로 가는 간선은 최단경로에 포함되지 않을 수도 있습니다.

경우에 따라서는 이 간선을 고려해줘야할 것 같습니다.

rhino333 7년 전 0

두 정점 사이에 간성이 여러개인 경우를 말씀하시는 건가요??

ntopia 7년 전 1

아니요 그냥 간단한 경우로

0->1 가중치 2

1->2 가중치 2

2->3 가중치 2

0->3 가중치 10

이렇게 4개 점과 4개 간선이 있다고 하고, 0번에서 출발해 3번으로 간다고 해봅시다.

이런 경우에 답을 제대로 구하지 못할 것 같습니다.

rhino333 7년 전 0

아 이런 반례가 있네요

간선을 지우지 않고 정점으로 처리해보려고 했는데

제 풀이는 이런 케이스를 처리 못하는군요.

간선을 지우는 풀이로 다시해봐야겠습니다.

감사합니다!

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

문제

문제

출처

ICPC

50%에서 틀리는데 원인을 못 찾겠습니다

rhino333 7년 전 0

ntopia 7년 전 1

rhino333 7년 전 0

ntopia 7년 전 1

rhino333 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말