[백준] 5214 환승

옛날에 풀어본 문제여서 다시 풀어보려고 했는데 탈탈 털렸다

옛날에는 어떻게 풀었을까? 도움을 받았었나 ㅎㅎ

 

이 문제는 하이퍼링크는 연결되어있기 때문에 안에서는 비용이 안들고

하이퍼링크를 넘어갈 때는 비용이 든다는걸 그래프로 표현해야한다

 

어떻게 해야할까..!

그래프를 만들때 (N+M)개의 정점으로 만들어주면 된다!

 

1~N 까지는 정점이고 (N+1 + M)까지는 바로 하이퍼링크..!

 

내가 어떤 점 X 가 하이퍼링크 K에 속해있다면

그래프 X에서는 갈 수 있는 하이퍼링크 K에 연결시켜주고 1의 비용이 들고

반대로 하이퍼링크 K 에서는 갈 수 있는 점들 X를 연결하고

하이퍼링크 안에서 이동이므로 비용은 0이 된다!

 

그래서 그래프를 만들면

 

X -> K (비용 1) 하이퍼링크 밖에서 이동 (정점 X를 가진 하이퍼링크 K로 이동)

K -> X (비용 0) 하이퍼링크 안에서 이동 (하이퍼링크 K에 속한 정점들로 이동)

 

이런 개념으로 만들어진다

 

어렵다..!

어떻게 생각할까 이런건 ㅎㅎ

 

그래프를 그려준다면 그 다음엔 최단거리 알고리즘으로 변한다!

다익스트라를 사용했다

 

소스코드

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
int n,m,k;
const int MAXN  =1e5+5;
int d[MAXN+1111];
 
int main(){
 
    scanf(" %d %d %d",&n,&k,&m);
    memset(d,-1,sizeof(d));
    vector<vector<pair<int,int>>> Graph(n+m+1);
    for(int i=n+1;i<n+m+1;i++){
        for(int j=0;j<k;j++){
            int x; scanf(" %d",&x);
            Graph[x].push_back({i,1});
            Graph[i].push_back({x,0});
        }
    }
    priority_queue<pair<int,int>> pq;
    pq.push({0,1});
 
    while(!pq.empty()){
        int now = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
 
        if(d[now] != -1) continue;
        d[now]=cost;
 
        for(int i=0;i<Graph[now].size();i++){
            int next = Graph[now][i].first;
            int ncost = -cost -Graph[now][i].second;
            if(d[next]==-1) pq.push({ncost,next});
        }
    }
 
    printf("%d\n",(d[n]==-1) ? -1 : d[n]+1);
}