1504번

1504번 - 특정한 최단 경로

1번 정점에서 N번 정점까지 가는데 A,B를 무조건 거쳐야 한다.

그러기 위해서는 1->A->B->N 이거나 1->B->A->N 이어야 한다.

( 문제에서 간선을 여러번 지나쳐도 되기 때문에, 다른 케이스는 고려하지 않아도 된다.)

따라서 첫번째 경우나, 두번째 경우에서 최솟값을 찾으면 된다.

편의상 D[i][j] 를 i 에서 j 가는 최단거리라고 하면 ,

첫번째 경우는 D[1][A] + D[A][B] + D[B][N] 이고,

두번째 경우는 D[1][B] + D[B][A} + D[A][N] 이 된다.

여기서 D[A][B]=D[B][A] 이므로 한번의 다익스트라 알고리즘으로 구하고,

D[1][A] 와 D[1][B]는 시작점을 1로 하는 다익스트라 알고리즘으로 구하고,

D[B][N]=D[N][B], D[A][N]=D[N][A] 이므로 시작점을 N으로 하는 다익스트라 알고리즘으로 구한다.

총 세번의 다익스트라 알고리즘으로 구할 수 있다.

모든 쌍들을 구해서 풀 수도 있으므로 플로이드-워셜 알고리즘으로 한꺼번에 구할 수도 있다.

### int 형 변수 범위 넘어가는 거 꼭 조심!

<정답 코드 - 다익스트라 (priority Queue 사용)>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 987654321;
int n, e, m1, m2;
long long from1toM1, from1toM2, fromM1toM2, fromNtoM1, fromNtoM2;
void dikjstra(int start, vector<vector<pair<int, int>>> v, vector<int> dist)
{
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
 
    priority_queue<pair<int, int>> q;
 
    dist[start] = 0;
    q.push({ start,0 });
 
    while (!q.empty())
    {
        int now = q.top().first;
        int cost = -q.top().second;
        q.pop();
 
        if (cost > dist[now]) 
        {
            continue;
        }
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (dist[next] > cost + w && cost != INF)
            {
                dist[next] = cost + w;
                q.push({ next,-dist[next] });
            }
        }
    }
 
    if (start == 1)
    {
        from1toM1 = dist[m1];
        from1toM2 = dist[m2];
    }
 
    if (start == m1)
    {
        fromM1toM2 = dist[m2];
    }
 
    if (start == n)
    {
        fromNtoM1 = dist[m1];
        fromNtoM2 = dist[m2];
    }
 
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &e);
    vector<vector<pair<int, int>> > v(n+1);
    vector<int> dist(n+1);
 
    int start = 1, dest = n;
 
    for (int i = 0; i < e; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
    scanf("%d %d", &m1, &m2);
 
    dikjstra(1,v,dist);
    dikjstra(m1,v,dist);
    dikjstra(n,v,dist);
    
    long long x = from1toM1 + fromM1toM2 + fromNtoM2;
    long long y = from1toM2 + fromM1toM2 + fromNtoM1;
 
    if (x >= INF && y >= INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", min(x, y));
    }
 
    return 0;
}

<정답 코드 - 다익스트라(priority Queue 사용하지 않음)>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 987654321;
int n, e, m1, m2;
long long from1toM1, from1toM2, fromM1toM2, fromNtoM1, fromNtoM2;
void dikjstra(int start, vector<vector<pair<int, int>>> v, vector<int> dist,vector<bool> visited)
{
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
 
    dist[start] = 0;
 
    while (true)
    {
        int now;
        int smallest = INF;
 
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i] && dist[i] < smallest)
            {
                now = i;
                smallest = dist[i];
            }
        }
 
        if (smallest == INF)
        {
            break;
        }
 
        visited[now] = true;
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int cost = v[now][i].second;
 
            if (dist[next] > cost + smallest)
            {
                dist[next] = cost + smallest;
            }
        }
    }
    
 
    if (start == 1)
    {
        from1toM1 = dist[m1];
        from1toM2 = dist[m2];
    }
 
    if (start == m1)
    {
        fromM1toM2 = dist[m2];
    }
 
    if (start == n)
    {
        fromNtoM1 = dist[m1];
        fromNtoM2 = dist[m2];
    }
 
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &e);
    vector<vector<pair<int, int>> > v(n+1);
    vector<int> dist(n+1);
    vector<bool> visited(n + 1);
    int start = 1, dest = n;
 
    for (int i = 0; i < e; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
    scanf("%d %d", &m1, &m2);
 
    dikjstra(1,v,dist,visited);
    dikjstra(m1,v,dist,visited);
    dikjstra(n,v,dist,visited);
    
    long long x = from1toM1 + fromM1toM2 + fromNtoM2;
    long long y = from1toM2 + fromM1toM2 + fromNtoM1;
 
    if (x >= INF && y >= INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", min(x, y));
    }
 
    return 0;
}

<정답 코드 - 플로이드 워샬 알고리즘>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
long long D[801][801];
const long long INF=987654321;
int main()
{
    int n, e; 
    vector<vector<pair<int, int>>> v;
    scanf("%d %d", &n, &e);
    int start = 1, dest = n;
    for (int i = 0; i < e; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        D[a][b] = c;
        D[b][a] = c;
    }
    int m1, m2;
    scanf("%d %d", &m1, &m2);
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                D[i][j] = 0;
            }
            else
            {
                if (D[i][j] == 0)
                {
                    D[i][j] = INF;
                }
            }
        }
    }
 
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
 
    long long ans = D[1][m1] + D[m1][m2] + D[m2][n];
    long long ans2 = D[1][m2] + D[m2][m1] + D[m1][n];
 
    if (ans >= INF && ans2>=INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%lld\n", min(ans, ans2));
    }
 
 
    
 
    return 0;
}