글 읽기 - 다음 큐에 넣는 값이 같지만 하나는 오답 하나는 정답인 이유를 모르겠습니다.

scyang91 4년 전 0

24번 줄을 q.push({ v[x][i], build_t[v[x][i]] + cur}); 에서 q.push({ v[x][i], spent[v[x][i]]});로 바꾸면 정답입니다.

spent[v[x][i]] = cur + build_t[v[x][i]];

같은 값인데 오답인 이유가 뭔가요?

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

int N;
vector <int> v[501];
int build_t[501];
int head[501];
int spent[501];
queue <pair<int, int> > q;
void sort_head() {
	while (!q.empty()) {
		int x = q.front().first;
		int cur = q.front().second;
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			if (cur + build_t[v[x][i]] > spent[v[x][i]])
				spent[v[x][i]] = cur + build_t[v[x][i]];
			head[v[x][i]]--;
			if (head[v[x][i]] == 0) 
				q.push({ v[x][i], build_t[v[x][i]] + cur});
		}
	}
}
int main() {
	cin >> N;
	int tmp, time;
	for (int i = 1; i <= N; i++) {
		cin >> time;
		build_t[i] = time;
		while (1) {
			cin >> tmp;
			if (tmp == -1) break;
			v[tmp].push_back(i);
			head[i]++;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (head[i] == 0) {
			q.push({ i, build_t[i] });
			spent[i] = build_t[i];
		}
	}
	sort_head();
	for (int i = 1; i <= N; i++) {
		cout << spent[i] << "\n";
	}
	return 0;
}

djm03178 4년 전 0

if (cur + build_t[v[x][i]] > spent[v[x][i]])

가 거짓이면 같지 않습니다.

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

문제

문제

출처

ICPC

다음 큐에 넣는 값이 같지만 하나는 오답 하나는 정답인 이유를 모르겠습니다.

scyang91 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말