글 읽기 - 제 접근법이 잘못된걸까요?

kdk8361 5년 전 0

입력받으면서 가중치에 일괄적으로 *= 2
여우는 가중치 그대로 dijkstra , 저장은 d1
늑대는 0 = 달리기 전, 1 = 달린 후로 나눠서 상태를 바꿔가며 가중치에 *2, /2 해주면서 dijkstra, d2에 저장
d1[i] < min(d2[i][0], d2[i][1])면 ans++

순으로 풀었습니다. 잘못된점 지적해 주시면 감사하겠습니다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;

typedef long long ll;

struct edge {
	ll v, w;
};

int n, m;
vector<edge> adj[4041];
ll d1[4041];
ll d2[4041][2];

int main() {
	memset(d1, -1, sizeof(d1));
	scanf(" %d %d ", &n, &m);
	while (m--) {
		ll u, v, w;
		scanf(" %lld %lld %lld ", &u, &v, &w);
		w *= 2;
		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
	}

	// 여우 dijkstra
	priority_queue<pair<ll, ll>> q;
	q.push({ 0,1 });
	while (q.size()) {
		ll x = q.top().second;
		ll c = -q.top().first;
		q.pop();
		if (d1[x] != -1) continue;

		d1[x] = c;
		for (auto i : adj[x]) {
			if (d1[i.v] != -1) continue;
			q.push({ -c - i.w, i.v });
		}
	}

	for (int i = 1; i <= n; ++i) d2[i][0] = d2[i][1] = 2e9;

	// 늑대 dijkstra
	priority_queue<pair<ll, pair<ll, ll>>> q2;
	q2.push({ 0,{ 1,0 } });
	while (q2.size()) {
		ll x = q2.top().second.first;
		ll c = -q2.top().first;
		ll f = q2.top().second.second;
		q2.pop();
		if (d2[x][f] != 2e9) continue;

		d2[x][f] = c;
		for (auto i : adj[x]) {
			ll nc = f ?  i.w * 2 : i.w / 2;
			if (d2[i.v][1 - f] != 2e9) continue;
			q2.push({ -c - nc,{ i.v, 1 - f } });
		}
	}


	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (d1[i] < min(d2[i][0], d2[i][1])) 
			ans++;
	}
	printf("%d\n", ans);
	return 0;
}

upple1 5년 전 1

문제에 나오는 그래프는 서로다른 두 점에 대한 경로가 있음을 보장하지 않기 때문에 아마 갈 수 없는 경로도 있을 것 같습니다.

그런데 d1을 초기화 할 때는 -1로 하고 d2를 초기화 할때는 INF로 하면서 만약 갈 수 없는 경로에 대해서 따져봤을 때 -1<INF가 되기 때문에 카운트를 합니다.

kdk8361 5년 전 0

감사합니다 ㅠㅠ 문제를 제대로 읽었어야 하는데

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

문제

문제

출처

ICPC

제 접근법이 잘못된걸까요?

kdk8361 5년 전 0

upple1 5년 전 1

kdk8361 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말