[백준 15591] Moo Tube

www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

문제대로 풀면 TLE 발생

 

처음 접근 방법: 플로이드 와샬 알고리즘처럼 모든 경로에서의 최단 거리를 구하려했다. TLE 발생

 

-> 개선: BFS 사용. 모든 경로에서의 최단 거리를 구할 필요가 없다.

조건이 있는 BFS 문제였다. 

문제의 목적은 start노드에서 USADO가 K이상인 노드 수를 세는 게 목적이다.

i->a의 USADO는 min(i->j, j->a)이다.

i->j, j->a둘 중에 하나라도 K보다 작다면? a로 가는 USADO는 K보다 작을 것이다. 따라서 탈락

 

그래서 우리는 출발노드에서 거리가 K이상인 노드만 큐에 담고 그 수를 셀 것이다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

bool visit[5001];
vector<pair<int, int>> v[5001];
int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  int n, q;

  cin >> n >> q;

  for (int i = 0; i < n - 1; i++)
  {
    int from, to, val;
    cin >> from >> to >> val;
    v[from].push_back(make_pair(to, val));
    v[to].push_back(make_pair(from, val));
  }

  for (int i = 0; i < q; i++)
  {
    int k, start;
    cin >> k >> start;
    memset(visit, false, sizeof(visit));
    queue<int> q;
    int cnt = 0;

    q.push(start);
    visit[start] = true;

    while (!q.empty())
    {
      int front = q.front();
      q.pop();
      for (int i = 0; i < v[front].size(); i++)
      {
        int next = v[front][i].first;
        if (visit[next])
          continue;

        int val = v[front][i].second;
        if (val >= k)
        {
          cnt++;
          visit[next] = true;
          q.push(next);
        }
      }
    }
    cout << cnt << "\n";
  }

  return 0;
}