글 읽기 - 50% 에서 틀렸다고 나옵니다 ㅠㅠ 도와주세요!!

dustn9401 7년 전 0

저는 다익스트라로 최대경로를 구하는 방법으로 해봤는데요

어떤 건물을 짓는데 필요한 건물이 0개면 (진입차수가 0이면) 처음에 짓는 건물이고, 여기서 도착점까지의 최대 경로를 구하는 방법으로

풀어봤는데요.

질문검색에 있는 예제들은 다 돌아가는데 (20개 정도)생각하지 못했던 예외가 있는것인지 틀렸다고 나와요................ 그것도 50%에서.......

어떤 부분에서 틀렸는지 알려주실 분~~~

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#define MAX_INT 1000000000
using namespace std;
typedef pair<int, int> pi;
int big(int a, int b)
{
	if(a >= b) return a;
	else return b;
};
class Graph {
public:
	vector<vector<int>> adj;
	vector<int> time;    //각 건물의 건설시간 저장
	int NumVertex;
	void insert(int start, int end)
	{
		adj[start].push_back(end);
	}
	int dijkstra(int, int);
	Graph(int num)
	{
		NumVertex = num;
		adj.resize(num);
		time.assign(num, 0);
	}
};
int Graph::dijkstra(int start, int end)    //최대 경로 탐색함수
{
	vector<int> d(NumVertex,-MAX_INT);
	vector<bool> visited(NumVertex,false);
	priority_queue<pi> pq;
	d[start] = time[start];
	pq.push({ d[start],start });
	while (!pq.empty())
	{
		int CurNode = pq.top().second;
		int CurWeight = pq.top().first;
		pq.pop();
		if (visited[CurNode]) continue;
		visited[CurNode] = true;
		for (int i = 0; i < adj[CurNode].size(); i++)
		{
			int NextNode = adj[CurNode][i];
			int NextWeight = time[NextNode];
			if (NextWeight + CurWeight > d[NextNode] && !visited[NextNode])
			{
				d[NextNode] = NextWeight + CurWeight;
				pq.push({ d[NextNode],NextNode });
			}
		}
	}
	return d[end];
}
int main()
{
	int tcase;
	scanf("%d", &tcase);
	while (tcase--)
	{
		int n, k, w;
		scanf("%d%d", &n, &k);
		Graph g(n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &g.time[i]);
		}
		vector<int> v(n,0);    //각 노드의 진입차수 저장할 변수
		for (int i = 0; i < k; i++)
		{
			int start, end;
			scanf("%d%d", &start, &end);
			start -= 1, end -= 1;
			g.insert(start, end);
			++v[end];    //도착점에 해당하는 노드의 진입차수 +1
		}
		scanf("%d", &w);
		w -= 1;
		int max = 0;
		for (int i = 0; i < n; i++)
		{
			if (v[i] == 0)    //진입차수가 0이면 시작건물이고, 시작건물이 여러개 일 수도 있으므로
                                //모든 시작점에 대한 최댓값을 구한다.
			{
				max = big(max, g.dijkstra(i, w));
			}
		}
		printf("%d\n", max);
	}
	return 0;
}

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

문제

문제

출처

ICPC

50% 에서 틀렸다고 나옵니다 ㅠㅠ 도와주세요!!

dustn9401 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말