[백준] 16763 - Fine Dining (c++)

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

 

문제 요약

정점이 N개이고 간선이 M개인 무방향 그래프가 주어진다. K개에 정점에 건초 묶음이 있고 각각 맛의 정도가 다르다. 1~N-1번 정점에 소가 한마리씩 있고 N번 정점으로 이동해야 한다. 소는 건초 묶음이 있는 점점에 들르기만 하면 건초를 먹을 수 있고 한 정점의 건초를 여러 소가 먹을 수 있다. 각 소에게 (건초를 먹는 경로-건초 맛)<=(최단경로)인 건초를 먹는 경로가 존재하는지 구해라.

 

풀이 (MlogN)

• 다익스트라

다익스트라를 두 번 돌려서 풀 수 있다. N번 정점을 시작으로 다익을 한 번 돌려 각 건초더미에서 N번 정점으로 가는 최단경로를 구해준다. 건초더미를 모두 시작 정점으로 설정하고 시작 가중치를 (건초더미->N 경로 - 맛)으로 설정해 다익을 한 번 돌려주면 (건초를 거쳐 N으로 가는 경로-맛)의 최소를 구할 수 있다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k;cin>>n>>m>>k;
    vector<vector<array<int,2>>> adj(n+1);
    for(int i=0,u,v,c;i<m;i++)
        cin>>u>>v>>c,adj[u].push_back({v,c}),adj[v].push_back({u,c});
    vector<int> dis1(n+1,1e9),dis2(n+1,1e9);
    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
    pq.push({dis1[n]=0,n});
    
    auto dij = [&](vector<int>& dis) {
        while(pq.size()) {
            auto [cc,u] = pq.top();pq.pop();
            if(dis[u]<cc)continue;
            for(auto[v,c]:adj[u]) {
                if(dis[v]>c+cc)
                    dis[v]=c+cc,pq.push({c+cc,v});
            }
        }
    };  
    dij(dis1);
    for(int i=0,u,c;i<k;i++)
        cin>>u>>c,pq.push({dis2[u]=dis1[u]-c,u});
    dij(dis2);

    for(int i=1;i<n;i++)
        cout<<(dis2[i]<=dis1[i]?1:0) <<'\n';
}