글 읽기 - 33%에서 틀립니다. 주석있습니다

idjjm95 2년 전 0

제가 생각하기에는

특정 경로를 지나는 최단 경로와 dijkstra로부터 구한 start~end까지의 최단거리가

같다면, 최종 후보지로 생각될 수 있다고 생각했습니다.

이 경우에 최단 경로가 많은 경우에도 풀 수 있다고 생각되는데

혹시 왜 33%에서 틀리는지 여쭤볼 수 있을까요?

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<algorithm>
#include<queue>
#define INF 20000000

using namespace std;

int d[2001]; // 객관적인 최단 경로

int n, m, t;
int s, g, h;
vector <pair<int, int>> graph[2001];
vector <int> dist[2001];			//경로를 지나는 최단 거리

struct comp {
	bool operator()(pair<int, int> & LHS, pair <int, int> & RHS)
	{
		return LHS.second > RHS.second;
	}
};

void dijkstra(int start)
{
	for (int i = 1; i <= n; i++)
		d[i] = INF;
	priority_queue<pair<int, int>, vector<pair<int, int>>, comp> PQ;
	d[start] = 0;

	PQ.push(make_pair(start, 0));

	while (!PQ.empty())
	{
		int distance = PQ.top().second;
		int cur = PQ.top().first;
		PQ.pop();
		if (distance > d[cur]) continue;
		for (int i = 0; i < graph[cur].size(); i++)
		{
			int next = graph[cur][i].first;
			int nextDistance = distance + graph[cur][i].second;
			if (nextDistance < d[next])
			{
				d[next] = nextDistance;
				PQ.push(make_pair(next, nextDistance));
			}
		}

	}
}

int main() {
	int T;
	int a, b, D;
	vector <int> sed; //후보
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		scanf("%d %d %d", &n, &m, &t);
		scanf("%d %d %d", &s, &g, &h);
		for (int j = 0; j < m; j++) // 경로만들기
		{
			scanf("%d %d %d", &a, &b, &D);
			graph[a].push_back(make_pair(b, D));
			graph[b].push_back(make_pair(a, D)); 
		}

		for (int j = 0; j < t; j++) {
			int a;
			scanf("%d", &a);		// 후보 입력
			sed.push_back(a);
		}

		sort(sed.begin(), sed.end());
		//알고리즘 설계, 다익스트라를 통해 start부터 최단 경로를 만들고, 주어진 경로를 지나는 경로로 부터 최단거리와 다를 때 그 목적지는 후보 목적지에서부터 빠진다.
		
		for (int j = 0; j < t; j++)
		{
			int result = INF;
			
			for (int k = 0; k < 2; k++) { //최적경로에 대한 비용 탐색
				int sum = 0;
				dijkstra(s);
				if (k == 0) {  // start -> g -> h -> destination
					sum += d[g];
					dijkstra(g);
					sum += d[h];
					dijkstra(h);
				//	sum += d[sed[j]];
				}
				if (k == 1)		//start -> h -> g-> destination
				{
					//dijkstra(s);
					sum += d[h];
					dijkstra(h);
					sum += d[g];
					dijkstra(g);
					
				}
				sum += d[sed[j]];
				result = min(result, sum); //최소값
			}
			
			dist[sed[j]].push_back(result);		//dist[후보지] = 대입
		}
		dijkstra(s);						//start와 최단거리 비교하기 위해 다시
		//각 거리와 비교
	
		for (int j = 0; j < t; j++)
		{
			if (dist[sed[j]][0] == d[sed[j]])		//경로를 지나는 최단거리와 같으면 후보지를 출력한다.
				printf("%d ", sed[j]);
		}
		printf("\n");
		
		//초기화
		for (int num1 = 1; num1 <= n; num1++){
			//for (int num2 = 0; num2 < graph[num1].size(); num2++) {
				graph[num1].clear();
				sed.clear();
				vector <pair<int, int>> ().swap(graph[num1]);
				vector <int>().swap(sed);
			}

	}

	
	return 0;
}

zenith82114 2년 전 1

105줄에서 dist의 각 벡터들에 값을 push_back 하므로

112줄의 dist[sed[j]][0]은 언제나 첫 번째 테스트 케이스 때의 값입니다.

idjjm95 2년 전 0

제가 잘 이해가 안돼서 그런데 ㅠㅜ

그래서 각 케이스가 끝나면 그래프랑 sed를 초기화해 주면서

각 케이스의 dist를 비교해주려고 했는데

혹시

이 부분과는 조금 다른경우인가요??

zenith82114 2년 전 1

보여주신 코드의 115줄과 117줄 사이에 A코드를 넣고

문제에 있는 예제를 실행하면 B와 같은 결과가 나옵니다.

1번째 테스트 케이스(이하 TC)에서 후보 도착지가 4, 5이므로

4의 dist는 12, 5의 dist는 11이라고 잘 계산되어 들어갔고 답도 맞았습니다.

그러면 이제 이 값들은 더 이상 필요가 없습니다. 그런데...

2번째 TC에서 후보 도착지는 5, 6이므로 5와 6의 dist가 계산되는데

5의 dist는 이번에도 11이고,

dist[5]가 int 변수가 아니라 vector이기 때문에

1번째 TC 때 5의 dist였던 11은 그대로 남아 있고 그 뒤에 이번 TC의 값인 11이 들어가고,

112줄에서 사용하는 dist[5][0]의 값은 지금 계산한 11이 아니라 아까 1번째 TC 때의 11인 것입니다.

이 예제는 정말 운 좋게 통과가 된 거죠.

// A
for (int j = 0; j < t; j++) {
    printf("dist[%d]:", sed[j]);
    for (int& k : dist[sed[j]])
        printf(" %d", k);
    printf("\n");
}

// B
4 5 
dist[4]: 12
dist[5]: 11
6 
dist[5]: 11 11
dist[6]: 6

idjjm95 2년 전 0

답변 감사합니다!

코드를 다시 한 번 생각해봐야겠습니다!!

정말 감사합니다!

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

문제

문제

출처

ICPC

33%에서 틀립니다. 주석있습니다

idjjm95 2년 전 0

zenith82114 2년 전 1

idjjm95 2년 전 0

zenith82114 2년 전 1

idjjm95 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말