[백준] 27630 - Unique Ability (c++)

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

 

문제 요약

간선마다 타입이 있는 무방향 가중치 그래프가 주어진다. 간선을 지나려면 플레이어와 간선의 타입이 같아야 한다. 플레이어의 타입을 바꾸는데 타입의 차이만큼 비용이 들 때 1에서 N으로 가는 최단경로의 비용을 구해라.

 

풀이 (MlogM)

• 다익스트라

한 정점에 대해 연결된 간선의 타입들을 저장해둔다. 정점을 (번호,타입) 쌍으로 나누어 같은 번호 인접한(정렬 순서) 타입끼리 간선을 만들어준다.

이렇게 새로 구성한 그래프에서 다익스트라를 한 번 돌려서 최단경로를 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    map<array<ll,2>,vector<array<ll,3>>> adj;
    vector<vector<ll>> vv(n+1);
    for(int i=0,u,v,c,t;i<m;i++)
        cin>>u>>v>>t>>c,
        adj[{u,t}].push_back({v,t,c}),adj[{v,t}].push_back({u,t,c}),
        vv[u].push_back(t),vv[v].push_back(t);
    
    map<pair<ll,ll>,ll> dis;
    for(int i=1;i<=n;i++) {
        vv[i].push_back(1);
        sort(vv[i].begin(),vv[i].end());
        dis[{(ll)i,vv[i][0]}]=1e18;
        for(int j=1;j<vv[i].size();j++)
            dis[{(ll)i,vv[i][j]}]=1e18,
            adj[{i,vv[i][j]}].push_back({i,vv[i][j-1],vv[i][j]-vv[i][j-1]}),
            adj[{i,vv[i][j-1]}].push_back({i,vv[i][j],vv[i][j]-vv[i][j-1]});
    }

    priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
    pq.push({dis[{1,1}]=0,1,1});
    while(pq.size()) {
        auto [cc,u,ct]=pq.top();pq.pop();
        if(dis[{u,ct}]<cc)continue;
        for(auto [v,t,c]:adj[{u,ct}]) {
            if(dis[{v,t}]>cc+c)
                pq.push({dis[{v,t}]=cc+c,v,t});
        }
    }
    cout<<dis[{n,1}];
}