글 읽기 - 반례를 모르겠습니다. 왜틀린지 이유를 모르겠습니다.

minjae200 5년 전 0

설명은 주석 그대로입니다. 다익스트라를 사용했습니다.

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

#define MAX_V 800
#define INF 987987654321
bool visited[MAX_V];
vector<pair<int, int>> adj[MAX_V];
int dist[MAX_V];


void dijktra(int start)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	fill(visited, visited + MAX_V, false);
	fill(dist, dist + MAX_V, INF);
	dist[start] = 0;
	pq.push(make_pair(0, start));
	while (!pq.empty()) {
		int curr;
		do {
			curr = pq.top().second;
			pq.pop();
		} while (visited[curr] && !pq.empty());
		if (visited[curr]) break;
		visited[curr] = true;
		for (auto p : adj[curr]) {
			int next = p.first;
			int d = p.second;
			if (dist[next] > dist[curr] + d) {
				dist[next] = dist[curr] + d;
				pq.push(make_pair(dist[next], next));
			}
		}
	}
}

int main(void)
{
	int N, E;
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w));
	}
	int mustindex_1, mustindex_2;
	cin >> mustindex_1 >> mustindex_2;
	int ans = 0;
	int OneToV1, OneToV2, V1ToV2, V1ToN, V2ToN;
	//dijktra(start);
	// 1-> mustindex_1   1->mustindex_2 최단거리 구할수잇음
	dijktra(1);
	OneToV1 = dist[mustindex_1];
	OneToV2 = dist[mustindex_2];
	if (OneToV1 >= INF && OneToV2 >= INF) {
		cout << "-1" << endl;
		return 0;
	}
	// mustindex_1 -> mustindex_2 == mustindex_2 -> mustindex_1
	dijktra(mustindex_1);
	V1ToV2 =  dist[mustindex_2];
	if (V1ToV2 >= INF) {
		cout << "-1" << endl;
		return 0;
	}
	//N-> mustindex_1     N->mustindex_2
	dijktra(N);
	V1ToN = dist[mustindex_1];
	V2ToN = dist[mustindex_2];
	if (V1ToN >= INF && V2ToN >= INF) {
		cout << "-1" << endl;
		return 0;
	}
	ans = min(OneToV1 + V1ToV2 + V2ToN, OneToV2 + V1ToV2 + V1ToN);
	if (ans >= INF) cout << "-1" << endl;
	else cout << ans << endl;
	return 0;
}

djm03178 5년 전 0

INF가 int의 범위를 넘습니다. int의 자릿수를 넘는 부분을 자르고 표현하면 145176241이 되는데 dist 배열에는 그렇게 잘려서 들어가므로 INF와 비교해도 INF를 넘을 수가 없습니다.

그리고 정점 번호가 800번까지 있으니 MAX_V는 최소한 801 이상이 되어야 합니다.

minjae200 5년 전 0

ㅏ감사합니다. 문제를 제대로 읽어야겠네요

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

문제

문제

출처

ICPC

반례를 모르겠습니다. 왜틀린지 이유를 모르겠습니다.

minjae200 5년 전 0

djm03178 5년 전 0

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말