[BOJ 13911] 집 구하기

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

해당문제의 경우 맥세권과 스세권의 최소거리를 구하는 문제이다. 그냥 다익스트라를 하면 되는 문제이지만 이 문제의 경우 V의 범위가 10000까지이므로 집에서 다 구하는경우 당연히 시간초과.

해결 방법은 집들에서 다익스트라를 돌리는것이 아니라 그냥 스벅들과 맥도날드 지점에서 다익스트라를 돌려서 각 집까지 거리가 얼마나 되는지 구하면 되는 문제이다. 해당문제의 경우 생각보다 아이디어 떠올리는데는 시간이 얼마 안걸렸지만 11번의 WA;;;

음 .그 실수한 부분은... 바로 스벅에서 집을 갈 때 스벅->집-> 집..-> 도착 이것이 아니라 맥도날드를 거쳐서 가는 경우가 더 빠를수 있다는 것이다. 

일단 코드를 첨부하면 

#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<math.h>
#define INF 1e15
typedef long long ll;
 
using namespace std;
 
int n,e,mn,sn,sv,mv,arr[11111];
ll distM[11111],distS[11111];
vector<vector<pair<int,int>>> v;
vector<int> mm;
vector<int> ss;
 
 
void solve1(){
    queue<int> q;
    for(int i=0;i<mm.size();i++){
        q.push(mm[i]);
    }
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for(int i=0;i<v[t].size();i++){
            if(distM[v[t][i].first] > distM[t]+v[t][i].second){
                distM[v[t][i].first] = distM[t]+v[t][i].second;
                q.push(v[t][i].first);
            }
        }
    }
}
 
void solve2(){
    queue<int> q;
    for(int i=0;i<ss.size();i++){
        q.push(ss[i]);
    }
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for(int i=0;i<v[t].size();i++){
            if(distS[v[t][i].first] > distS[t]+v[t][i].second){
                distS[v[t][i].first] = distS[t]+v[t][i].second;
                q.push(v[t][i].first);
            }
        }
    }
}
 
 
 
int main(){
    memset(arr,0,sizeof(arr));
    
    cin >> n >>e;
    v.resize(n+1);
    for(int i=1;i<=n;i++){
        distM[i] = INF;
        distS[i] = INF;
    }
    
    for (int i=1; i<=e; i++) {
        int a,b,c;
        cin >> a >> b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    
    cin >> mn>>mv;
    
    for(int i=1;i<=mn;i++){
        int a;
        cin >> a;
        arr[a] = 1;
        mm.push_back(a);
        distM[a] = 0;
    }
    
    cin >> sn>>sv;
    for(int i=1;i<=sn;i++){
        int a;
        cin >> a;
        arr[a] = 2;
        ss.push_back(a);
        distS[a] = 0;
    }
    
    solve1();
    solve2();
    ll ans = INF;
    for(int i=1;i<=n;i++){
        if(arr[i] == 0 && distM[i] <=mv && distS[i] <=sv){
            ans = min(ans , distM[i]+distS[i]);
        }
    }
    if(ans == INF){
        printf("-1\n");
    }else {
        printf("%lld\n" ,ans);
    }
}
 
 

주의해야할 점이 바로 32번째 if문이었다. 나는 이때 arr[i] == 0일떄 (즉 집에서 집으로 이동할때만 처리함) 만 처리를 해주었었는데 그거 빼니까 맞더라 ;; 

암튼