백준 1277 발전소 설치

 

https://www.acmicpc.net/problem/1277

 

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>


#define INF 987654321

using namespace std;


pair<int, int> chg[1001];
vector<pair<double, int>> g[1001];



double dist[1001];


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, w;
    double m;

    cin >> n >> w;

    cin >> m;

    //dist 배열 초기화
    fill_n(&dist[0], n + 1, INF);


    for (int i = 1; i <= n; i++) {
        cin >> chg[i].first >> chg[i].second;
    }

    for (int i = 0; i < w; i++) {
        pair<int, int> conn;
        cin >> conn.first >> conn.second;

        //이미 연결되어 있는 전선은 길이 0으로 처리
        g[conn.first].push_back({0, conn.second});
        g[conn.second].push_back({0, conn.first});
    }

    //조건에 맞는 모든 전선을 잇기
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {

            double d = sqrt(pow(chg[j].second - chg[i].second, 2) + pow(chg[j].first - chg[i].first, 2));

            if (d <= m) {

                g[i].push_back({d, j});
                g[j].push_back({d, i});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
    }



    //1번 발전소에서 시작하는 다익스트라

    dist[1] = 0;
    queue<int> q;
    q.push(1);


    while (!q.empty()) {

        int cur = q.front();
        q.pop();

        for (int i = 0; i < g[cur].size(); i++) {

            if (dist[g[cur][i].second] > dist[cur] + g[cur][i].first) {
                dist[g[cur][i].second] = dist[cur] + g[cur][i].first;
                q.push(g[cur][i].second);
            }

        }
    }


    if (dist[n] == INF) {
        cout << -1;
    } else {
        cout << (long long)floor(1000 * dist[n]);
    }





    return 0;
}

 

격자에 배치된 노드 중 조건에 맞는(d<=m) 노드들을 연결하고 최솟값을 구하는 문제이다.

입력받은 모든 노드에 대하여 거리를 계산, m을 넘으면 연결하지 않는다.

단, 이미 연결된 노드라면 거리를 0으로 하여 연결한다.

 

1->n의 최단거리를 구하는 문제이므로 1부터 다익스트라를 사용하여 거리를 계산하고, n까지의 최솟값을 출력한다.