글 읽기 - 6%에서 틀리는데 예제는 맞다고 나오는데,, 반례를 알고싶어요

boysoeng 1년 전 0

다익스트라 알고리즘으로 DAG 찾고,

DAG에서 위상정렬을 한 후, dp를 이용해 문제를 풀었습니다.

예제는 맞게 나오는데 6%에서 계속 틀리네요 ㅠ

반례나 오류 찾아주시면 감사하겠습니다.

모든 조언 감사히 받겠습니다.

#include<iostream>
#include<vector>
#include<queue>
#include<stack>

#define MAX_V 200020
#define INT_MAX 2147483647

using namespace std;
typedef long long lng;

vector<pair<int, int>> edge[MAX_V];//dist[start]에 (end, dist)의 배열이 들어있음.
vector<pair<int, int>> edge2[MAX_V];//DAG를 저장할 벡터
vector<int> redge2[MAX_V];//dp를 구할때 필요한 벡터

int dist[MAX_V];
int prev1[MAX_V];
vector<int> res;//위상정렬 결과 배열


void djikstra(int st) {//시작점1부터 갈 수 있는 모든 정점에 도달하는 최단경로

	int visited[MAX_V] = { 0, };
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;//greater이므로 first가 낮은 순서대로
	dist[st] = 0;
	pq.push({ 0,st });
	while (!pq.empty()) {
		int cur = pq.top().second; pq.pop();
		if (visited[cur])continue;
		visited[cur] = 1;


		for (auto& i : edge[cur]) {
			int nx = i.first;
			int cost = i.second;
			int next_dist = dist[cur] + cost;
			if (dist[nx] >next_dist) {
				dist[nx] = next_dist;
				prev1[nx] = cur;
				pq.push({ dist[nx],nx });
			}

		}
	}
}





int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		int w; cin >> w;
		edge[x].push_back({ y,w });//start, end, weight
		edge[y].push_back({ x,w });//양방향 그래프
	}
	int cnt = 0;
	int* note = new int[MAX_V];
	for (int i = 1; i <= n; i++) {
		cin >> note[i];
		if(note[i]==1)cnt++;//cnt = 전체 노트조각의 개수
	}
	fill(dist, dist + MAX_V, INT_MAX);
	fill(prev1, prev1 + MAX_V, -1);
	djikstra(1);

	int* innerdot = new int[MAX_V];
	fill(innerdot, innerdot + n + 1, 0);

	for (int i = 1; i <= n; i++) {
		for (auto j : edge[i]) {
			if (dist[j.first] == dist[i] + j.second) {
				edge2[i].push_back(j);//i->j.fisrt의 간선
				redge2[j.first].push_back(i);
				innerdot[j.first]++;
			}
		}
	}//DAG 생성
	//위상정렬해야함

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (innerdot[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		res.push_back(cur);
		for (auto i : edge2[cur]) {
			int w = i.first;
			innerdot[w]--;
			if (innerdot[w] == 0)q.push(w);
		}
	}
	delete[]innerdot;
	int* dp = new int[MAX_V];
	int* dp2 = new int[MAX_V];
	fill(dp, dp + MAX_V, 0);
	fill(dp2, dp2 + MAX_V, 0);
	

	//dp[i] : 1->i까지 오는 경로에서 주울 수 있는 노트조각의 개수
	vector<int> path;
	for (auto i : res) {
		int mx = 0; int mxidx = 0;
		for (int j = 0; j < redge2[i].size();j++) {
			int w = redge2[i][j];
			if (dp[w] > mx) {
				mx = dp[w];
				mxidx = w;
			}
		}
		
		dp[i] = mx + note[i];
		dp2[i] = mxidx;
		
	}
	


	if (dp[n] == cnt) {//최단경로와 dp가 같으면, 최단경로 출력
		cout << dp[n] << "\n";
		int tmp = n;
		stack<int> st;
		while (tmp) {
			st.push(tmp);
			tmp = dp2[tmp];
		}
		while (!st.empty()) {
			cout << st.top() << " ";
			st.pop();
		}
		cout << "\n";

	}
	else cout << "-1\n";

	delete[] dp;
    delete[] dp2;
	delete[] note;
	return 0;
}

xorjs1011 1달 전 1

이미 해결하셨겠지만 첫 줄에는 '방문하는 정점의 개수'를 출력하셔야 합니다.

먹은 노트 조각 개수를 출력하시면 안돼요.

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

문제

문제

출처

ICPC

6%에서 틀리는데 예제는 맞다고 나오는데,, 반례를 알고싶어요

boysoeng 1년 전 0

xorjs1011 1달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말