글 읽기 - 최단거리 4% 틀렸다고 나옵니다. 어디를 손 봐야 될까요? 반례라도..

위 두 글에서 나온 반례는 모두 통과 합니다.

그리고 INF값이 낮아서 3백만으로 바꿔줬는데 안되고,

다음 갈 정점의 기준을 가중치 말고 dst누적합 중 가장 적은 것으로 해도 틀리네요?

정점과 간선이 둘 다 1일 경우가 원인이라 생각했는데 그건 또 아닌 것같네요;;

만약

~~1 1~~

~~1 3 3 처럼 출발 도착이 다르면 정점이 두 개가 아니라서 inf(없는 정점에 갈 수 없으니까)~~

만약

~~1 1~~

~~4 4 4 출발 도착이 같으면 그 자리에 있으니까 0출력~~

ps:제가 굳이 따로 if문 안줘도 1개 짜리 케이스 처리가 되네요. 그래서 없앴다만, 여전히 4%에서 에러 뜨네요

도데체 원인이 뭘까요;;

#include <vector>
#include <queue>
#include <cstdio>

using namespace std;
int dst[20001];

/* 수정 후 알고리즘. size변수를 따로 두었는 데, 쓸모 없으니 지움*/
int main()
{   
	for (int i = 1; i <= 20000; i++)
	{
		dst[i] = 3000000; //3백만을 inf로 지정
	}

	

	struct cmp
	{
		bool operator() (pair<int, int> left, pair<int, int> right)
		{

			return dst[left.first] > dst[right.first];
		}
	};//누적 거리가 낮은 순으로 방문 예정리스트 정렬

	vector<pair<int, int>> edges [20001];
	int V, E, K;
	scanf("%d %d", &V, &E);
	scanf("%d", &K);

	dst[K] = 0; //시작점은 무조건 0
	
	int from, to, weight;
	for (int i = 0; i < E; i++)
	{
		scanf("%d %d %d", &from, &to, &weight);
		edges[from].push_back(make_pair(to, weight));
		//벡터에 삽입
	}


	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>new_cur;
	int cnt = V;
	int cur = K;
	while (cnt > 0)
	{
		while (edges[cur].size() > 0)
		{
			if (dst[cur] + edges[cur].front().second < dst[edges[cur].front().first])
			{  //비교문 
				dst[edges[cur].front().first] = dst[cur] + edges[cur].front().second;
			}
				new_cur.push(edges[cur].front());//방문 예정 큐에 삽입
           	
			edges[cur].erase(edges[cur].begin()); //벡터에서 요소 제거
		}
	

		if (new_cur.empty() == true) // 더 이상 갈 곳이 없으면 루프문 탈출
		{
			break;
		}
		
		cur = new_cur.top().first;//시작지점 갱신
		new_cur.pop();
	
		cnt--;
	}



	for (int i = 1; i <= V; i++)//출력파트
	{
	 if (dst[i] == 3000000)
		{
			printf("INF\n");
		}
		else
		{
			printf("%d\n", dst[i]);
		}

	}

}


/*#include <vector>
#include <queue>
#include <cstdio>

using namespace std;
int dst[20001]; //정점별 거리 값


int main()
{   
	for (int i = 1; i <= 20000; i++)
	{
		dst[i] = 3000000; // 처음에 모두 INF로 초기화 INF값은 3백만
	} 

	

	struct cmp  // 다음에 들릴 정점을 정렬하는 함수. 누적 거리 값이 낮은 순으로 정렬
	{
		bool operator() (pair<int, int> left, pair<int, int> right)
		{

			return dst[left.first] > dst[right.first];
		}
	};

	vector<pair<int, int>> edges [20001]; // 정점별 간선을 저장할 벡터 배열
	int V, E, K;  // 정점 수, 간선 수, 시작점 받기
	scanf("%d %d", &V, &E);
	scanf("%d", &K);

	dst[K] = 0;  // 시작점은 0으로 초기화
	int size[20001] = { 0, }; // 정점 별 간선 개수 
	int from, to, weight;// 시작, 도착, 가중치 받기
	for (int i = 0; i < E; i++)
	{
		scanf("%d %d %d", &from, &to, &weight);
		edges[from].push_back(make_pair(to, weight));
		size[from]++;
	}
    
    if(V==1&&E==1)  // 정점, 간선 둘 다 1일 때
    {
        if(from ==to) // 출발 도착이 같으면
        {
            printf("0");
            return 0;
        }  //아니면 
        printf("INF");
        return 0;
    }
    

	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>new_cur; // 다음 갈 정점 저장
	int cnt = V; 
	int cur = K; // 시작점 저장
	while (cnt >= 0) //정점 개수 만큼까지만 돌림
	{
		while (size[cur]>0) // 안에 든게 없으면 나감
		{
			if (dst[cur] + edges[cur].front().second < dst[edges[cur].front().first])
			{//현위치+목적지 가중치가 dst[목적지] 보다 낮으면 갱신
				dst[edges[cur].front().first] = dst[cur] + edges[cur].front().second;
			}
			new_cur.push(edges[cur].front()); // 연결된 간선을 방문예정 큐에 저장
			
			edges[cur].erase(edges[cur].begin()); // 한 번 확인 간선을 벡터에서 제거
			size[cur]--;
		}
	

		if (size[cur] == 0 && new_cur.empty() == true) //더 이상 접근 가능한 정점이 없으면 끝
		{
			break;
		}
		
		cur = new_cur.top().first; //시작점 갱신
		new_cur.pop();//방문리스트에서 제거
	
		cnt--;
	}



	for (int i = 1; i <= V; i++) //출력파트
	{
	 if (dst[i] == 3000000)
		{
			printf("INF\n");
		}
		else
		{
			printf("%d\n", dst[i]);
		}

	}

}*/

wlgh5014 1년 전 0

종료여부를 방문예정 큐가 비었는 지 안비었는 지로 바꾸고, 거리가 갱신될 때 만 업데이트 했더니 13%에서 틀리네요. 계속 일지를 올리겠습니다.

	new_cur.push(make_pair(cur, 0));
	while (new_cur.empty() != true)
	{
		while (edges[cur].size() > 0)
		{
			if (dst[cur] + edges[cur].front().second < dst[edges[cur].front().first])
			{
				dst[edges[cur].front().first] = dst[cur] + edges[cur].front().second;
				new_cur.push(edges[cur].front());

			}

			edges[cur].erase(edges[cur].begin());
		}

wlgh5014 1년 전 0

기존에는 벡터 size함수로 해당 노드에 연결된 간선들을 계산하고, 계산 후 그냥 지워 버렸는데,

혹시나 다시 돌아 왔을 때 간선들의 dst 값이 달라 졌을 경우가 떠올라서 혹시 몰라 그냥 안 삭제 하는 쪽으로 했더니 맞았습니다.

for (vector<pair<int,int>>::iterator it = edges[cur].begin(); it != edges[cur].end(); ++it)
		{

			if (dst[cur] + it->second < dst[it->first])
			{
				dst[it->first] = dst[cur] + it->second;
				new_cur.push(make_pair(it->first,it->second));

			}
		}

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

문제

문제

출처

ICPC

최단거리 4% 틀렸다고 나옵니다. 어디를 손 봐야 될까요? 반례라도..

wlgh5014 1년 전 0

wlgh5014 1년 전 0

wlgh5014 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말