백준 15591 - MooTube (Silver)(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

그래프 탐색을 이용해 푸는 문제였습니다.

시작점을 큐에 넣고 탐색을 시작하지 않는 것이 중요했습니다.

시작점이 아닌 시작점과 연결된 점들을 큐에 넣은 뒤 탐색을 시작해, 최단 거리를 구해주면 됐습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 2000000000

using namespace std;

int N, Q;
vector<P> connect[5001];
int Distance[5001][5001];

void bfs(int start){
    queue<P> q;
    Distance[start][start] = 0;
    for(int i = 0; i < connect[start].size(); i++){
        q.push({connect[start][i].F, connect[start][i].S});
    }
    while(!q.empty()){
        int x = q.front().F;
        int cost = q.front().S;
        Distance[start][x] = cost;
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = min(connect[x][i].S, cost);
            if(Distance[start][xx] == INF){
                q.push({xx, n_cost});
            }
        }
    }
}

void solve(){
    int cost, start;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            Distance[i][j] = INF;
        }
    }
    for(int i = 1; i <= Q; i++){
        cin >> cost >> start;
        int ans = 0;
        if(Distance[start][start] == INF) bfs(start);
        for(int j = 1; j <= N; j++){
            if(Distance[start][j] >= cost) ans++;
        }
        cout << ans << "\n";
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> Q;
    for(int i = 1; i < N; i++){
        int x, y, cost;
        cin  >> x >> y >> cost;
        connect[x].push_back({y, cost});
        connect[y].push_back({x, cost});
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요