글 읽기 - 1504 질문입니다.

chatterboy 9년 전 0

특정한 두 정점 v1, v2를 반드시 지나야하므로 0 -> v1 -> v2 -> V-1 라고 생각하고 각 경로별로 다익스트라를 적용했습니다.

그리고 적어도 한 경로가 INT_MAX라면 -1을 출력하도록 구현을 했는데 왜 오답이 뜰까.. 고민하다가 질문합니다.

#include <cstdio>
#include <climits>

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

typedef struct _edge {
	int v;
	int weight;
} edge;

int V, E;
int sv, fv;
vector <bool> intree;
vector <int> distances;
vector <int> parent;
vector < vector <edge> > edges;

void dijkstra(int start) {
	int v;

	for (v = 0; v < V; v++) {
		intree[v] = false;
		distances[v] = INT_MAX;
		parent[v] = -1;
	}

	distances[start] = 0;
	v = start;

	while (intree[v] == false) {
		int dist;
		int e;
		int vv;

		intree[v] = true;

		// 정점 v에 인접한 정점 w들의 distances[w]와 parent[w]를 업데이트
		for (e = 0; e < (int)edges[v].size(); e++) {
			int v1, w1;
			v1 = edges[v][e].v;
			w1 = edges[v][e].weight;

			// distances[w]가 distances[v] + weight[v][w]보다 크면 업데이트
			if (distances[v1] > (distances[v] + w1) ) {
				distances[v1] = distances[v] + w1;
				parent[v1] = v;
			}
		}

		v = 0;
		dist = INT_MAX;
		// intree에 포함되지 않은 정점들 중 distances가 가장 작은 정점을 선택한다
		for (vv = 0; vv < V; vv++) {
			// intree에 포함되지 않은 정점들 중
			// 가장 작은 distances를 가지는 정점이다
			if ((intree[vv] == false) && (dist > distances[vv]) ) {
				dist = distances[vv];
				v = vv;
			}
		}
	}
}

void solve(void) {
	// 세 개의 구간에 대한 세 개의 답을 구하고
	// 세 개의 답에서 INT_MAX가 하나도 없으면 참값
	// 적어도 한 개가 존재하면 -1을 출력
	int ans1, ans2, ans3;

	dijkstra(0);
	ans1 = distances[sv - 1];
	dijkstra(sv - 1);
	ans2 = distances[fv - 1];
	dijkstra(fv - 1);
	ans3 = distances[V - 1];

	if ((ans1 != INT_MAX) && (ans2 != INT_MAX) && (ans3 != INT_MAX) ) {
		printf("%d", ans1 + ans2 + ans3);
	} else printf("-1");
}

void input(void) {
	int e;

	scanf("%d %d", &V, &E);

	edges.resize(V);
	for (e = 1; e <= E; e++) {
		edge ee1, ee2;
		int v1, v2, w;
		scanf("%d %d %d", &v1, &v2, &w);

		// 정점 v1의 인접 정점 v2와 가중치 w를 저장
		ee1.v = v2 - 1;
		ee1.weight = w;

		edges[v1 - 1].push_back(ee1);

		// 정점 v2의 인접 정점 v1와 가중치 w를 저장
		ee2.v = v1 - 1;
		ee2.weight = w;

		edges[v2 - 1].push_back(ee2);
	}

	scanf("%d %d", &sv, &fv);

	intree.resize(V);
	distances.resize(V);
	parent.resize(V);
}

int main(void) {
	input();

	solve();

	return 0;
}

sujin 9년 전 3

1->v2->v1->V 일 수도 있습니다

h0ngjun7 9년 전 1

0->v2->v1->V-1일 수도 있습니다

chatterboy 9년 전 0

아 그렇군요 !!

감사합니다 :)

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

문제

문제

출처

ICPC

1504 질문입니다.

chatterboy 9년 전 0

sujin 9년 전 3

h0ngjun7 9년 전 1

chatterboy 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말