글 읽기 - 어느 부분이 틀린건가요?

ojh031 4년 전 0

예제는 잘 나오고 조건도 다 확인해서 J의 이동거리가 더 작게 했고 같은 경우에는 더 작은 수가 나오도록 확인도 했습니다.

혹시 다익스트라 알고리즘이 잘못된 건가요?

#include <iostream>
#include <queue>
using namespace std;

#define INF 987654321;

int V,M;
int arr[101][101];
int J,S;
int a[101];
bool visit[101];

void dik(int s){
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int c=q.front();
		q.pop();
		visit[c]=true;
		for(int i=1;i<=V;i++){
			if(a[i]>a[c]+arr[c][i]){
				a[i]=a[c]+arr[c][i];
				if(!visit[i]){
					q.push(i);
				}
			}
		}
	}
}
void init(){
	int aa,b,c;
	cin>>V>>M;
	for(int i=1;i<=V;i++){
		for(int j=1;j<=V;j++){
			arr[i][j]=INF;
			if(i==j)
				arr[i][j]=0;
		}
		a[i]=INF;
	}
	for(int i=0;i<M;i++){
		cin>>aa>>b>>c;
		arr[aa][b]=c;
		arr[b][aa]=c;
	}
	cin>>J>>S;
}	
int main(){
	init();
	a[J]=0;
	dik(J);
	int aj[101];
	for(int i=1;i<=V;i++){
		aj[i]=a[i];
		a[i]=INF;
		visit[i]=false;
	}
	a[S]=0;
	dik(S);
	int smallest=INF;
	int smidx=-1;
	for(int i=1;i<=V;i++){
		if(i==S || i==J) continue;
		if(smallest>a[i]+aj[i] && aj[i]<=a[i]){
			smallest=a[i]+aj[i];
			smidx=i;
		}
		else if(smallest==a[i]+aj[i]){
			if(a[smidx]<a[i])
				smidx=i;
		}
	}
	cout<<smidx<<endl;
	return 0;
}

windflower 4년 전 1

네 다익스트라 알고리즘이 잘못된 것 같습니다.

ojh031 4년 전 0

죄송하지만 어느부분이 잘못된 것 인지 알 수 있을까요? 큐는 우선순위 큐로 바꾸었습니다.

같은 방법으로 1916번 문제 풀어보니 제대로 풀리는데 문제가 뭔지 도무지 모르겠습니다

windflower 4년 전 1

@ojh031 바꾸신 코드 다시 올려주시겠어요?

ojh031 4년 전 0

이렇게 수정했습니다.

#include <iostream>
#include <queue>

using namespace std;

#define INF 987654321;

int V,M;
int arr[101][101];
int J,S;
int a[101];
bool visit[101];

void dik(int s){
	priority_queue<pair<int,int>> q;
	q.push({0,s});
	while(!q.empty()){
		int c=q.top().second;
		q.pop();
		visit[c]=true;
		for(int i=1;i<=V;i++){
			if(a[i]>a[c]+arr[c][i]){
				a[i]=a[c]+arr[c][i];
				if(!visit[i]){
					q.push({-1*(a[c]+arr[c][i]),i});
				}
			}
		}
	}
}
void init(){
	int aa,b,c;
	cin>>V>>M;
	for(int i=1;i<=V;i++){
		for(int j=1;j<=V;j++){
			arr[i][j]=INF;
			if(i==j)
				arr[i][j]=0;
		}
		a[i]=INF;
	}
	for(int i=0;i<M;i++){
		cin>>aa>>b>>c;
		arr[aa][b]=c;
		arr[b][aa]=c;
	}
	cin>>J>>S;
}
int main(){
	init();
	a[J]=0;
	dik(J);
	int aj[101];
	for(int i=1;i<=V;i++){
		aj[i]=a[i];
		a[i]=INF;
		visit[i]=false;
	}
	a[S]=0;
	dik(S);
	int smallest=INF;
	int smidx=-1;
	for(int i=1;i<=V;i++){
		if(i==S || i==J) continue;
		if(smallest>a[i]+aj[i] && aj[i]<=a[i]){
			smallest=a[i]+aj[i];
			smidx=i;
		}
		else if(smallest==a[i]+aj[i]){
			if(a[smidx]<a[i])
				smidx=i;
		}
	}
	cout<<smidx<<endl;
	return 0;
}

windflower 4년 전 1

다익스트라 코드도 위 코드는 최악의 경우 시간복잡도가 달라질 수 있습니다만 이 문제 정답 여부에서는 영향이 없을 것 같으므로 차치하겠습니다... (djm03178 님이 쓰신 글 참고하시면 좋을 것 같아요! http://www.secmem.org/blog/201...)

65번째 줄 if문에서 '최단거리에 속하는 정점들 중에서 가능여부'를 판단해야 하는데 최단거리를 잘못 측정하는 경우가 생기지 않을까요??

ojh031 4년 전 0

해당 소스 참고해서 다시 처음부터 작성해보았는데 여전히 답을 찾을 수가 없네요..

저 코드와 다른점이 visit밖에 없어서 visit을 제외하고 코드를 다시 작성했는데 여전히 틀렸다고 나오는데 도무지 그 이유를 모르겠습니다.. 혹시 다른 힌트 더 받을 수 있을까요?

#include <iostream>
#include <queue>
#include <limits.h>
using namespace std;

int V, M; 
long long g[1001][1001];
int a, b, c;
int J, S;
long long mapJ[1001], mapS[1001];


long long* dik(long long map[1001], int s) {
	map[s] = 0; //첫점을 0으로
	//bool visit[1001] = { false };
	priority_queue<pair<int, int>> pq; //first : 가중치 second : 중간 경유지점
	pq.push({ 0,s }); //처음은 출발점으로
	while (!pq.empty()) {
		pair<int, int> cur = pq.top();
		pq.pop();
		//visit[cur.second] = true;
		if (cur.first > map[cur.second]) {
			continue;
		}
		for (int i = 1; i <= V; i++) {
			if (map[cur.second] + g[cur.second][i] < map[i]) {
				map[i] = map[cur.second] + g[cur.second][i];
				pq.push({ -1*map[i] , i });
			}
		}
	}
	return map;
}
void initialize() {
	cin >> V >> M;
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			g[i][j] = INT_MAX;
		}
		mapJ[i] = INT_MAX;
		mapS[i] = INT_MAX;
	}// 도달할 수 없다는 것을 -1로 표시
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		g[a][b] = c;
		g[b][a] = c; //initialize
	}
	cin >> J >> S;
}
int main() {
	initialize();
	dik(mapJ, J);
	dik(mapS, S);

	long long sum[1001];
	for (int i = 1; i <= V; i++) 
		sum[i] = mapJ[i] + mapS[i];

	int minidx=-1;
	long long minnum = INT_MAX;
	for (int i = 1; i <= V; i++) {
		if (i == S || i == J)
			continue;
		if (minnum > sum[i] && mapJ[i]<=mapS[i]) {
			minnum = sum[i];
			minidx = i;
		}
		if (minnum == sum[i] && mapJ[minidx] > mapJ[i])
			minidx = i;
	} //최솟값을 찾음
	
	cout << minidx << endl;
	
	return 0;
	
}

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

문제

문제

출처

ICPC

어느 부분이 틀린건가요?

ojh031 4년 전 0

windflower 4년 전 1

ojh031 4년 전 0

windflower 4년 전 1

ojh031 4년 전 0

windflower 4년 전 1

ojh031 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말