BOJ 17940 - 지하철

문제 태그 : https://www.acmicpc.net/problem/17940

문제 소개

출발지에서 목적지까지 지하철을 타고 이동한다. 각 지하철역은 A회사 또는 B회사의 소유인데 방문하는 지하철역의 변경횟수를 최소화 하면서 이동을 해야한다. 만약 횟수가 최소인 경로가 여러가지가 있으면, 경로의 길이가 가장 짧은 경로를 선택한다. 이때 최소 변경횟수와 경로의 길이를 출력하라.

문제 풀이  

사전지식 + 간단한 아이디어 하나로 바로 해결할 수 있다. 
1. 일단 경로를 구하는것이고 시작점->도착점 하나이기 때문에 기본문제면 다익스트라를 이용해 해결 할 수 있다.
2. 결국 중요한 것은 지하철역 회사가 바뀌는 경로이다.
3. 똑같은 위치로 이동할 때 다른 경로를 아무리 길게 해도 회사가 바뀌는 경로로 가는 것이 훨씬 안좋다.

따라서 간선의 가중치에 살짝 조작을 해보자!
회사가 바뀌는 경로의 간선은 간선의 가중치에 1e9를 더한 값으로 매긴다. inf=1e18
이렇게 하면 그냥 다익을 돌려도 특정 간선을 최대한 안 지나는 방향으로 진행할 수 있다.
이때 최종 경로 값에서 1e9로 나눈 값이 변경 횟수이고 나머지가 경로의 길이가 될 것이다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
ll in[1010][1010];
ll arr[1010101];
vector<pii> v[1010];
ll dis[1010101];
 
void dijk(ll st){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,st});
    while(!pq.empty()){
        auto x=pq.top(); pq.pop();
        if(dis[x.ss]<x.ff) continue;
        for(auto n:v[x.ss]){
            if(dis[n.ss]>dis[x.ss]+n.ff){
                dis[n.ss]=dis[x.ss]+n.ff;
                pq.push({dis[n.ss],n.ss});
            }
        }
    }
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++){
        dis[i]=1e18;
        scanf("%lld",&arr[i]);
    }
    dis[1]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%lld",&in[i][j]);
 
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(in[i][j]){
                ll di=in[i][j];
                if(arr[i]+arr[j]==1) di+=1e9;
                v[i].pb({di,j});
            }
        }
    }
    dijk(1);
    //for(i=1;i<=n;i++)
    //    printf("%lld %lld\n",i,dis[i]);
 
    printf("%lld %lld",dis[m+1]/(ll)1e9,dis[m+1]%(ll)1e9);
    
}

아이디어가 살짝 섞인 좋은 문제였다고 생각한다.