[백준] 31602 - There and Back Again (c++)

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

 

문제 요약

가중치 있는 무방향 그래프가 주어진다. 1번 정점에서 n번 정점을 거쳐 1번 정점으로 돌아와야 한다. 다만 1에서 n으로 갈 때 거친 간선의 집합과 n에서 1로 갈 때 거친 간선의 집합이 같으면 안 된다. 최소 비용을 구해라.

 

풀이 (MlogN)

• 다익스트라

1에서 n으로 가는 다익을 한 번 돌리고 거친 간선의 집합을 저장해 놓는다. n에서 1로 가는 다익을 돌릴 땐 정점을 두배로 늘려서 한 번이라도 집합에 포함되지 않는 간선을 지난 정점과 아닌 정점을 구분한다. 

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

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    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});

    set<array<int,2>> spv;int ans=0;
    {
        priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
        int pre[n+1]{};
        vector<int> dis(n+1,1e18);
        pq.push({dis[1]=0,1});
        while(pq.size()) {
            auto [cc,u]=pq.top();pq.pop();
            if(dis[u]<cc) continue;
            for(auto [v,c]:adj[u]) {
                if(dis[v]>cc+c)
                    pq.push({dis[v]=cc+c,v}),pre[v]=u;
            }
        }
        ans+=dis[n];
        for(int i=n;i!=0;i=pre[i])
            spv.insert({i,pre[i]}),spv.insert({pre[i],i});
    }
    {
        priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
        vector<vector<int>> dis(n+1,vector<int>(2,1e18));
        pq.push({dis[1][0]=0,1,0});
        while(pq.size()) {
            auto [cc,u,f]=pq.top();pq.pop();
            if(dis[u][f]<cc) continue;
            for(auto [v,c]:adj[u]) {
                if(dis[v][f]>cc+c)
                    pq.push({dis[v][f]=cc+c,v,f});
                if(f) continue;
                if(spv.find({u,v})==spv.end()&& dis[v][1]>cc+c)
                    pq.push({dis[v][1]=cc+c,v,1});
            }
        }
        if(dis[n][1]==1e18)
            return cout<<-1,0;
        ans+=dis[n][1];
    }
    cout<<ans;
}