글 읽기 - 반례를 알 수 있을까요??

20rnjsekdns 2년 전 0

61%에서 계속 틀렸다고 뜹니다ㅠ

아무래도 dijkstra2() 함수에서 문제가 있는 게 아닐까 짐작을 하고 있습니다.

nextNode가 y라면 continue시켜버리는데 이것이 문제가 되는 걸까요?

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define MAX (100000 + 1)
#define INF 987654321
#define ll long long
#define pil pair<int, ll>
using namespace std;

vector<pil> graph[MAX];
int n, m;

struct cmp {
	bool operator()(pil& a, pil& b) {
		return a.second > b.second;
	}
};

vector<ll> dijkstra(int node) {
	priority_queue<pil, vector<pil>, cmp> pq;
	vector<ll> dist(n + 1, INF);
	dist[node] = 0;
	pq.push({ node, 0 });
	while (!pq.empty()) {
		int now = pq.top().first;
		ll cost = pq.top().second;

		pq.pop();
		//if (dist[now] < cost) continue;

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			ll nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push({ next, dist[next] });
			}
		}
	}
	return dist;
}

ll dijkstra2(int node, int y, int z) {
	priority_queue<pil, vector<pil>, cmp> pq;
	vector<ll> dist(n + 1, INF);
	dist[node] = 0;
	pq.push({ node, 0 });
	while (!pq.empty()) {
		int now = pq.top().first;
		ll cost = pq.top().second;

		pq.pop();
		//if (dist[now] < cost) continue;

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			ll nextCost = graph[now][i].second;

			if (next == y) continue;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push({ next, dist[next] });
			}
		}
	}
	return dist[z];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		graph[a].push_back({ b, w });
	}

	int x, y, z;
	cin >> x >> y >> z;
	vector<ll> fromX = dijkstra(x);
	vector<ll> fromY = dijkstra(y);

	if (fromY[z] == INF || fromX[y] == INF) cout << -1 << ' ';
	else {
		cout << fromX[y] + fromY[z] << ' ';
	}

	ll fromXtoZ = dijkstra2(x, y, z);

	if (fromXtoZ == INF) cout << -1;
	else cout << fromXtoZ;

	return 0;
}

iloveelsa 2년 전 0

저랑 같은 방법으로 푸신지는 모르겠습니다만, 저도 61%쯤 틀려서 코드를 고쳐보니 x에서 y를 거쳐서 z를 가는 과정(첫 번째 출력) 안에서, x에서 z를 거쳐서 y로 가거나 y에서 x를 거쳐서 z로 가는 경우를 다 포함해야 되더라구요

xingxing2001 2년 전 0

INF 값을 10^9 으로 설정하면 61퍼 뚫립니다.

해당 코드는 72퍼에서 TLE 가 나네요..

저는 INF 값을 123456789 로 했는데 도저히 안돼서 INF 값을 10^9으로 하니깐 61퍼에서 틀리던 코드 AC 받았습니다..

20rnjsekdns 2년 전 1

고마워요 덕분에 INF 값 정의가 잘못 되었다는 걸 알았어요!!

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

문제

문제

출처

ICPC

반례를 알 수 있을까요??

20rnjsekdns 2년 전 0

iloveelsa 2년 전 0

xingxing2001 2년 전 0

20rnjsekdns 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말