백준 1240 - 노드사이의 거리(C++)

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

1240번: 노드사이의 거리

M개 만큼 BFS를 수행하면 되는 문제였습니다.

먼저 노드와 cost를 백터를 통해 이어줍니다.

그 다음 M개만큼 시작점, 끝점을 받아 BFS를 돌려주면 됩니다.

이때 check의 값은 0이 아닌 -1로 해줘야지 조건이 편해집니다.

0로 거리의 값으로 포함되기 때문에 방문여부를 확인하기 위해서 -1를 저장해줬습니다.

 

또한, 구조가 트리이기 때문에 어느 곳을 먼저 방문했더라도 최단거리가 나옵니다.

-> 다익스트라가 아닌 BFS를 사용해도 되는 이유입니다.

 

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

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

using namespace std;

int N, M;
vector<P> connect[1001];
int check[1001];

int bfs(P A){
    memset(check,-1,sizeof(check));
    int start = A.F;
    int finish = A.S;
    queue<int> q;
    q.push(start); // 현재 좌표
    check[start] = 0; // X점까지의 비용
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x == finish) return check[x];
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int Cost = connect[x][i].S;
            if(check[xx] != -1) continue;
            q.push(xx);
            check[xx] = check[x] + Cost;
        }
    }
}

void solve(){
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        cout << bfs({x,y}) << "\n";
    }
}

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

 

 

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