글 읽기 - 1504번 특정 최단경로

persona_k 5년 전 0

어떤 부분이 잘못되었을까요?..

제출 부분에서 9퍼에서 틀렸습니다 뜨네요.

문제 풀이전략 간단하게)

특정 노드 2개를 거쳐서 가야하기 때문에

1 => v1 => v2 => N

1 => v2 => v1 => N

방식으로 각각 다익스트라를 6번 돌렸습니다.

도움 부탁드립니다. 읽어주셔서 감사합니다.

// 수정

다익스트라를 3번 돌리는 형식으로 고치고,

입력부분에서 더 작은 가중치가 들어오게 되면 그것을 갱신하는 방식으로 변경했는데에도,

틀렸다고합니다.

이유가 뭘까요?...

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

#define INF 10000000
#define MAX 801
int N, E, a, b, c, V1, V2;
int edge[MAX][MAX];
int visit[MAX];
int dist[MAX];

void init(int visit[], int dist[]) {
	for (int i = 1; i <= N; i++) {
		visit[i] = 0;
		dist[i] = 0;
	}
}

//start -> end로 구하는
void dijkstra(int start, int end, int dist[], int visit[]) {
	
	for (int i = 1; i <= N; i++) {
		if (edge[start][i] == 0) {
			dist[i] == INF;
		}
		else {
			dist[i] = edge[start][i];
		}
	}
	dist[start] = 0;
	visit[start] = 1;

	for (int i = 1; i <= N; i++) {

		int min = INF;
		int idx = 1;
		//인접한 가장 작은 가중치를 갖는 정점찾기
		for (int i = 1; i <= N; i++) {
			if (visit[i] == 0 && min > dist[i]) {
				min = dist[i];
				idx = i;
			}
		}
		visit[idx] = 1;
		for (int j = 1; j <= N; j++) {
			if (visit[j] == 0) {
				if (dist[j] > dist[idx] + edge[idx][j]) {
					dist[j] = dist[idx] + edge[idx][j];
				}
			}
		}
	}
}

int main()
{
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;

		if (edge[a][b] == 0) {
			edge[a][b] = c;
			edge[b][a] = c;
		}//더 작은 값이 있다면
		else if (edge[a][b] > c) {
			edge[a][b] = c;
			edge[b][a] = c;
		}
	}
	cin >> V1 >> V2;

	//최종목표 
	//1->V1->V2->N
	int one_route = 0;
	//1->V2->V1->N
	int two_route = 0;

	dijkstra(1, N, dist, visit);
	int path_1 = dist[V1]; // 1->V1
	int path_2 = dist[V2]; // 1->V2
	init(visit, dist);
	dijkstra(V1, V2, dist, visit);
	int path_3 = dist[V2]; // V1->V2, V2->V1
	init(visit, dist);
	dijkstra(N, 1, dist, visit);
	int path_4 = dist[2]; //N->2
	int path_5 = dist[3]; //N->3
	//cout << path_1 << " " << path_2 << " " << path_3 << " " << path_4 << " " << path_5 << endl;

	if (path_1 == INF || path_3 == INF || path_5 == INF)
		one_route = 1;
	if (path_2 == INF || path_3 == INF || path_4 == INF)
		two_route = 1;

	if (one_route == 1 && two_route == 1)
		cout << -1;
	else
		cout << min(path_1 + path_3 + path_5, path_2 + path_3 + path_4);

	return 0;
}

seico75 5년 전 0

34라인이 2부터 시작하는거가 맞나요?

그리고 양방향이라서 a b 거리가 같고

1대다 최단 거리 알고리즘리이니

1부터 v1과 v2

N부터 v1 v2

v1부터 v2

세번만 돌리면 안될까요?

persona_k 5년 전 0

듣고 보니 그렇네요 3번만 돌리면 가능하군여!!

답글 감사합니다.

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

문제

문제

출처

ICPC

1504번 특정 최단경로

persona_k 5년 전 0

seico75 5년 전 0

persona_k 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말