글 읽기 - 게시판 반례 다 확인해봤는데 틀렸다고 뜹니다 ㅜㅜ

jooyeok42 3년 전 0

마지막에 건축되어야 하는 건물을 기준으로 역방향으로 값을 더해나가며, 진입 노드가 여러개일때는 그중 최댓값을 현재 DP값으로 설정했습니다.
위상정렬을 써서 인접노드를 다 소모했을 때는 방문을 못하게 했는데 어떤게 잘못된것인지 잘 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int indegree[1001];
int createtime[1001];
int d[1001];
vector<int> a[1001];
queue<int> q;
int n, k, m, ans;
int maxi(int a,int b){
	if(a>b) return a;
	else return b;
}
int mini(int a,int b){
	if(a<b) return a;
	else return b;
}
void bfs(){
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i];
			d[y]=maxi(d[y],d[x]+createtime[y]);
			if(indegree[y]!=0 )q.push(y);
			indegree[y]--;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test;
	cin >> test;
	for(int t=0;t<test;t++){
		memset(d,0,sizeof(d));
		memset(createtime,0,sizeof(createtime));
		memset(indegree,0,sizeof(indegree));
		ans=0;
		for(int i=0;i<1001;i++){
			a[i].clear();
		}
		int n,k,victory;
		cin >> n >> k;
		for(int i=1;i<n+1;i++){
			cin >>  createtime[i];
		}
		for(int i=1;i<k+1;i++){
			int x,y;
			cin >> x >> y;
			a[y].push_back(x);
			indegree[x]++;
		}
		cin >> victory;
		d[victory]=createtime[victory];
		q.push(victory);
		bfs();
		for(int i=1;i<n+1;i++){
			ans = maxi(ans,d[i]);
		}
		cout << ans;
		if(t+1!=test) cout << "\n";
	}
}

djm03178 3년 전 2

반례입니다.

https://ideone.com/ZvkoMv

위상정렬에서 indegree를 사용하는 것은 이 코드에서 사용하는 것과는 반대입니다. indegree가 0이 되는 순간에만 큐에 넣어주어야 하고, 임의의 정점에서 시작하는 것이 아닌 indegree가 0인 모든 노드를 큐에 넣고 시작해야 합니다.

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

문제

문제

출처

ICPC

게시판 반례 다 확인해봤는데 틀렸다고 뜹니다 ㅜㅜ

jooyeok42 3년 전 0

djm03178 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말