[백준] 1504.cpp : 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

• 간선 간 양의 거리가 주어진 다익스트라 문제인데, 중간에 반드시 거쳐야 하는 점 두개가 주어진다.
• 처음엔 해당 노드들을 방문했는지 체크하는 요소를 추가해서 검사하려 했는데, 상당히 복잡해질 것 같아서 그만뒀다.
• 대신, 그냥 다익스트라로 1 ~ v1 ~ v2 ~ N 까지 각각의 최단거리들을 구해서 더한 값이 최단거리가 된다.
• 하지만 v1 과 v2 중 어디를 먼저 지나가냐에 따라 거리가 달라질 수 있기 때문에, 둘 다 구해서 더 작은 값을 취해준다.

---

#include <iostream>
#include <vector>
#include <queue>

#define INF 10e8

using namespace std;

int n, e, answer;
int a, b, c;
int v1, v2;
vector<pair<int,int>> nodes[801];

int dijkstra(int start, int end)                            // 시작점과 끝점이 주어졌을 때 다익스트라로 최단거리 반환
{
    int ret = -1;
    vector<int> visited(n+1, INF);                          // visited 배열은 각 인덱스(노드)의 최단거리 저장, INF 로 초기화

    priority_queue<pair<int,int>> pq;
    pq.push(pair<int,int>(0, start));                       // start 부터 시작
    visited[start] = 0;

    while(pq.size())
    {
        int pos = pq.top().second;                          // 이번 노드를 꺼내서 확인
        int dist = -pq.top().first;
        pq.pop();

        for(int i = 0 ; i < nodes[pos].size() ; i++)        // 노드에 연결되어있는 다른 노드들 모두 확인하는데
        {
            int nextPos = nodes[pos][i].second;
            int nextDist = nodes[pos][i].first;
            
            if(dist + nextDist < visited[nextPos])          // 최단거리 갱신이 가능한 노드들만 집어넣음
            {
                visited[nextPos] = dist + nextDist;         // 업데이트 해주고 큐에 푸시함
                pq.push(pair<int,int>(-(dist + nextDist), nextPos));
            }
        }
    }

    return (visited[end] == INF ? -1 : visited[end]);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> e;
    for(int i = 0 ; i < e ; i++)
    {
        cin >> a >> b >> c;
        nodes[a].push_back(pair<int,int>(c, b));                        // 간선 연결 (양방향)
        nodes[b].push_back(pair<int,int>(c, a));
    }
    cin >> v1 >> v2;

    int a1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);      // 1 ~ v1 ~ v2 ~ n 까지의 최단거리
    int a2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n);      // 1 ~ v2 ~ v1 ~ n 까지의 최단거리
    answer = min(a1, a2);
    if (answer == - 3) answer = -1;                                     // 둘 중 작은 값을 택한다

    cout << answer << endl;
}

---

 

---

• 1등 소스코드 참고 : www.acmicpc.net/source/5135510e
• int 입력을 따로 클래스를 만들어서 사용하셨다.
• 다익스트라를 6번 돌릴 필요 없이, 한번 돌렸을 때 visited 배열에 각각 해당 노드에서 다른 모든 노드들의 최솟값이 정해지므로, 1번 노드, v1 노드, v2 노드 3개에 대해서만 배열을 만들면 재활용이 가능하다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cctype>
using namespace std;
typedef pair<int,int> pii;

class FastIO
{
private:
    int fd;
    int bufsz;
    char* buf;
    char* cur;
    char* end;

public :
    FastIO(int _fd = 0, int _bufsz = 1 << 20) : fd(_fd), bufsz(_bufsz)
    {
        buf = cur = end = new char[bufsz];
    }
    ~FastIO()
    {
        delete[] buf;
    }
    bool readbuf()
    {
        cur = buf;
        end = buf + bufsz;
        while(true)
        {
            size_t res = fread(cur, sizeof(char), end - cur, stdin);
            if(res == 0) break;
            cur += res;
        }
        end = cur;
        cur = buf;
        return buf != end;
    }
    int readint()
    {
        while(true)
        {
            if(cur == end) readbuf();
            if(isdigit(*cur) || *cur == '-') break;
            ++cur;
        }
        bool sign = true;
        if(*cur == '-')
        {
            sign = false;
            ++cur;
        }
        int ret = 0;
        while(true)
        {
            if(cur == end && !readbuf()) break;
            if(!isdigit(*cur)) break;
            ret = ret * 10 + (*cur - '0');
            ++cur;
        }
        return sign? ret : -ret;
    }
};

FastIO fio;
const int INF = 10e8;
int n, e, s, t;
vector<pii> nodes[801];

void dijkstra(int st, vector<int>& d)
{
    priority_queue<pii> pq;
    d[st] = 0;
    pq.push({0, st});
    while(pq.size())
    {
        auto r = pq.top();
        pq.pop();
        int pos = r.second;
        int dist = -r.first;
        for(auto& iter : nodes[pos])
        {
            int nextPos = iter.first;
            int nextDist = dist + iter.second;
            if(nextDist < d[nextPos])
            {
                d[nextPos] = nextDist;
                pq.push({-nextDist, nextPos});
            }
        }
    }
}

int main()
{
    n = fio.readint();
    e = fio.readint();
    for(int i = 0 ; i < e ; i++)
    {
        int u = fio.readint();
        int v = fio.readint();
        int w = fio.readint();
        nodes[u].push_back({v, w});
        nodes[v].push_back({u, w});
    }
    s = fio.readint();
    t = fio.readint();

    vector<int> d1(n+1, INF);
    vector<int> ds(n+1, INF);
    vector<int> dt(n+1, INF);
    dijkstra(1, d1);
    dijkstra(s, ds);
    dijkstra(t, dt);
    int ans1 = d1[s] + ds[t] + dt[n];
    int ans2 = d1[t] + dt[s] + ds[n];
    int answer = min(ans1, ans2);
    if(answer >= INF) printf("%d\n", -1);
    else printf("%d\n", answer);
    return 0;
}