글 읽기 - 왜 통과가 되는지 모르겠습니다.

lsn1106 4년 전 1

https://www.acmicpc.net/board/view/21839

(글의 알고리즘 + 좌표압축을 하여 풀었습니다.)

19https://www.acmicpc.net/problem/2336

위 문제와 동일한 알고리즘을 사용했는데, 위 문제는 모든 값이 distinct하지만 이 문제는 중복될 수 있습니다.

<1>

	~A	~B	~C
1번	4	1	1
2번	5	2	3

위와 같은 경우, 2번정점에서의 A,B,C까지의 거리가 1번정점에서보다 모두 크기 때문에 2번 정점이 제외 됩니다

<2>

	A	B	C
1번	5	1	1
2번	5	2	3

하지만 위와 같은 경우, 1번 정점과 2번 정점의 A까지의 거리가 같기때문에 2번정점을 제외할 수 없습니다.

<2>번과 같은 경우때문에 제 알고리즘이 통과될 수 없다고 생각되는데, 왜 통과가 되는걸까요?

(제 생각엔, 체크배열을 세개 만들어서 A,B,C 기준으로 모두 돌려봐야 정당한 풀이가 되지 않나 싶습니다.)

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;
const int MAX = 1e5 + 4;
const int SMAX = (1 << 18);
const int INF = 0x3f3f3f3f;

int n, m, seg[SMAX], st[3], d[3][MAX];
vector<P> g[MAX];
T dist[MAX];
bool vst[MAX], chk[MAX];

void update(int i, int x) {
	i += SMAX / 2;
	seg[i] = min(seg[i], x);
	while (i > 1) {
		i /= 2;
		seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
	}
}

int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return INF;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return min(val(s, e, node * 2, ns, mid), val(s, e, node * 2 + 1, mid + 1, ne));
}
int val(int s, int e) { return val(s, e, 1, 0, SMAX / 2 - 1); }


void maked(int i) { //st[i]~모든 지점까지의 거리
	memset(vst, 0, sizeof(vst));
	priority_queue<P, vector<P>, greater<P>> pq;
	d[i][st[i]] = 0;
	pq.push({ d[i][st[i]], st[i] });

	while (!pq.empty()) {
		int u = pq.top().second; pq.pop();
		if (vst[u]) continue;
		vst[u] = true;
		for (P p : g[u]) {
			int v, w; tie(v, w) = p;
			if (d[i][v] > d[i][u] + w) {
				d[i][v] = d[i][u] + w;
				pq.push({ d[i][v], v });
			}
		}
	}

	vector<int> s;
	for (int j = 1; j <= n; j++) s.push_back(d[i][j]);
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	for (int j = 1; j <= n; j++)
		d[i][j] = lower_bound(s.begin(), s.end(), d[i][j]) - s.begin();
}

int main() {
	FAST; cin >> n;
	for (int i = 0; i < 3; i++) cin >> st[i];
	cin >> m;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
	}

	memset(d, 0x3f, sizeof(d));
	for (int i = 0; i < 3; i++) maked(i);

	for (int i = 1; i <= n; i++) {
		get<0>(dist[i]) = d[0][i];
		get<1>(dist[i]) = d[1][i];
		get<2>(dist[i]) = d[2][i];
		get<3>(dist[i]) = i;
	}
	
	sort(dist + 1, dist + n + 1);
	memset(seg, 0x3f, sizeof(seg));
	for (int i = 1,x,y,z,id; i <= n; i++) {
		tie(x, y, z, id) = dist[i];
		
		if (y>0 && val(0, y - 1) < z) chk[id] = 1;
			
		update(y, z);
	}

	int query; cin >> query;
	while (query--) {
		int i; cin >> i;
		cout << (chk[i] ? "NO\n" : "YES\n");
	}
}

sheenjiwon 3년 전 0

매장 후보지 p에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 a, b, c라고 하고 다른 매장 후보지 q가 존재해서 q에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 x, y, z라고 할 때, a > x 이고 b > y 이고 c > z이면 p에는 매장을 설치하지 않는다.

위와 같이 명시되어 있으면 위에서 언급한 <2>번은 a > x 에 해당되지 않으므로 설치가 가능한 거 아닌가요?

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

문제

문제

출처

ICPC

왜 통과가 되는지 모르겠습니다.

lsn1106 4년 전 1

sheenjiwon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말