BOJ 12834 - 주간미팅

rivermt·2023년 3월 20일
0

BOJ

목록 보기
1/18

문제

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

팀원이 N명이 주어졌을 때 한 사람의 거리 d = (팀원의 집 ~ KIST의 최단거리) + (팀원의 집 ~ 씨알푸드의 최단거리)로 정의된다.
이때 KIST 또는 씨알푸드까지 도달하지 못한다면 최단거리는 -1로 정의된다.
(둘 다 도달하지 못하는 경우는 d = -2)

최종적으로 Σd 를 구하는 문제이다.

풀이

SOL1

우선 어떤 정점에서 목적지까지의 최단거리를 알아야하므로 다익스트라 알고리즘을 떠올렸다.
팀원의 수 N만큼 각각 다익스트라를 2번 (KIST, 씨알까지의 최단거리) 를 전부 더해주어 해결했다.

CODE

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <string>
    #include <cmath>
    using namespace std;
    typedef pair<int, int> pi;
    #define endl '\n'
    #define MAX 1e9

    int n, v, e;
    int k, s;

    vector<int>home, dist;
    vector<vector<pi>>adj;

    int dijk(int st, int ed) {
        vector<int>dist(v+1, MAX);
        priority_queue<pi>pq;
        
        pq.push({0, st});
        
        dist[st] = 0;
        
        while(!pq.empty()) {
            int now = pq.top().second;
            int cost = -pq.top().first;
            pq.pop();
            
            if(dist[now] < cost)continue;
            
            for(auto&node : adj[now]) {
                int next = node.second;
                int nc = dist[now] + node.first;
                
                if(nc >= dist[next]) continue;

                dist[next] = nc;
                
                pq.push({-nc, next});
                
            }
            
        }
        
        return dist[ed];
        
    }

    int getResult(int st) {
        int homeToKist = dijk(st, k);
        int homeToFood = dijk(st, s);
        
        homeToKist = homeToKist == MAX ? -1 : homeToKist;
        homeToFood = homeToFood == MAX ? -1 : homeToFood;
        
        return homeToKist + homeToFood;
        
    }

    int main(){
        
        scanf("%d %d %d", &n, &v, &e);
        scanf("%d %d", &k, &s);
        for(int i=0;i<n;++i){
            int loc;
            scanf("%d", &loc);
            home.push_back(loc);
        }
        
        adj.resize(v+1);

        for(int i=0;i<e;++i){
            int a, b, l;
            scanf("%d %d %d", &a, &b, &l);
            adj[a].push_back({l, b});
            adj[b].push_back({l, a});
        }
        
        int sum = 0;
        
        for(auto& x : home) {
            sum += getResult(x);
        }
        
        printf("%d\n", sum);
        
        return 0;
    }

SOL2

팀원을 시작점으로 생각해 다익스트라를 2*N 만큼 돌렸지만 생각해보니 KIST와 씨알푸드의 위치를 시작점으로 생각하고 팀원의 위치를 목적지로 생각한다면 다익스트라를 두 번만 돌려도 될 것이다.

다익스트라를 돌리는 횟수가 확 줄었기 때문에 시간이 많이 단축되었음을 확인할 수 있다.
시작점, 끝점을 잘 생각해서 적용하고 풀어보자!

CODE

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <string>
    #include <cmath>
    using namespace std;
    typedef pair<int, int> pi;
    #define endl '\n'
    #define MAX 1e9

    int n, v, e;
    int k, s;

    vector<int>home, dist;
    vector<vector<pi>>adj;

    int dijk(int st) {
        vector<int>dist(v+1, MAX);
        priority_queue<pi>pq;
        
        pq.push({0, st});
        
        dist[st] = 0;
        
        while(!pq.empty()) {
            int now = pq.top().second;
            int cost = -pq.top().first;
            pq.pop();
            
            if(dist[now] < cost)continue;
            
            for(auto&node : adj[now]) {
                int next = node.second;
                int nc = dist[now] + node.first;
                
                if(nc >= dist[next]) continue;

                dist[next] = nc;
                
                pq.push({-nc, next});
                
            }
            
        }
        
        int sum = 0;
        
        for(auto& x : home) {
            sum += (dist[x]==MAX) ? -1 : dist[x];
        }
        
        return sum;
        
    }

    int main(){
        
        scanf("%d %d %d", &n, &v, &e);
        scanf("%d %d", &k, &s);
        for(int i=0;i<n;++i){
            int loc;
            scanf("%d", &loc);
            home.push_back(loc);
        }
        
        adj.resize(v+1);

        for(int i=0;i<e;++i){
            int a, b, l;
            scanf("%d %d %d", &a, &b, &l);
            adj[a].push_back({l, b});
            adj[b].push_back({l, a});
        }
        
        
        printf("%d\n", dijk(k) + dijk(s));
        
        return 0;
    }
profile
화이팅!!

0개의 댓글