글 읽기 - 틀렸습니다 떳는데 어디서 잘못되었을까요?

richard0326 6년 전 0

bfs 형식으로 만들었습니다.

그리고 선행 노드를 여러 군대서 출발 할 수 있도록 만들었습니다.

최고로 건물 지어지는데 오래 걸리는 경우의 값을 구한다고 했는데, 틀렸나 봅니다.

어디서 문제가 있었을까요?

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

int* d;
int* a;
vector<int>* v;
queue<int> q;

void bfs(int start, int target)
{
   int f = q.front();
   q.pop();
   if (f == target)
   {
      return;
   }

   int size = v[f].size();
   for (int i = 0; i < size; i++)
   {
      q.push(v[f][i]);
      if (d[v[f][i]] == 0)
      {
         d[v[f][i]] = d[f] + a[f];
      }
      else if (d[v[f][i]] < d[f] + a[f])
      {
         d[v[f][i]] = d[f] + a[f];
      }
   }
   
   bfs(q.front(), target);
}

int main()
{
   int t;
   scanf("%d", &t);

   while (t--)
   {
      // 초기화
      int tempA[1001] = { 0, };
      a = tempA;
      vector<int> tempV[1001];
      for (int i = 0; i < 1001; i++)
      {
         tempV[i].clear();
      }
      v = tempV;

      bool check[1001] = { true, false, };

      int n, m;
      scanf("%d", &n);
      scanf("%d", &m);

      for (int i = 0; i < n; i++)
      {
         scanf("%d", &a[i+1]);
      }

      for (int i = 0; i < m; i++)
      {
         int c, d;
         scanf("%d", &c);
         scanf("%d", &d);
         v[c].push_back(d);
         check[d] = true;
      }

      int target;
      scanf("%d", &target);

      int mVal = 0;
      for (int i = 0; i < n; i++)
      {
         if (check[i + 1] == false)
         {
            while (!q.empty())
            {
               q.pop();
            }

            int tempD[1001] = { 0, };
            d = tempD;

            q.push(i+1);
            bfs(i + 1, target);

            if (mVal < d[target] + a[target])
            {
               mVal = d[target] + a[target];
            }
         }         
      }
      
      printf("%d\n", mVal);
   } 

   return 0;
}

sgchoi5 6년 전 0

힌트 보시면 아시겠지만 기본적인 해결방법은 위상정렬입니다.. bfs로는 처리가 힘들듯하니.... 위상정렬 한번 찾아보시길....

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

문제

문제

출처

ICPC

틀렸습니다 떳는데 어디서 잘못되었을까요?

richard0326 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말