[Algorithm]Baekjoon 1504번 :: 특정한 최단 경로

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

1504번: 특정한 최단 경로

#define MAX_NUM 100000000
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int v, e;
    int a, b, c;
    int ca, cb;
 
    cin >> v >> e;
 
 
    vector<vector<int>> adjArray(801, vector<int>(801, MAX_NUM));
 
    for (int i = 1; i <= v; i++)
    {
        adjArray[i][i] = 0;
    }
 
 
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b >> c;
 
        adjArray[a][b] = c;
        adjArray[b][a] = c;
    }
 
    cin >> ca >> cb;
 
    for (int m = 1; m <= v; m++)
    {
        for (int i = 1; i <= v; i++)
        {
            for (int j = 1; j <= v; j++)
            {
                if (adjArray[i][m] + adjArray[m][j] <= adjArray[i][j])
                {
                    adjArray[i][j] = adjArray[i][m] + adjArray[m][j];
                }
            }
        }
    }
 
    int route1 = adjArray[1][ca] + adjArray[ca][cb] + adjArray[cb][v];
    int route2 = adjArray[1][cb] + adjArray[cb][ca] + adjArray[ca][v];
 
    if (route1 >= MAX_NUM || route2 >= MAX_NUM) cout << -1;
    else
        cout << min(route1, route2);
}

특정 노드를 거치는 조건하에 N번 버텍스까지의 최단거리를 구하는 문제이다.

푸는 방법은 두가지가 있는데 플로이드와샬 or 다익스트라이다.

위의 코드는 플로이드와샬이며 시간제한에 걸리지 않고 통과는 한다.

다만, 확실히 성능은 조금 떨어지긴 해서 다익스트라로 코드를 한번 더 짜보고 비교해봤다.

 

아래가 다익스트라 코드.

 

#define MAX_NUM 100000000
 
struct Node
{
    int node;
    int distance;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.distance > b.distance;
    }
};
 
vector<vector<Node>> graph(801);
 
int djik(int start, int dest)
{
    priority_queue<Node, vector<Node>, cmp> pq;
    vector<int> dist(801, MAX_NUM);
    dist[start] = 0;
 
    pq.push({ start,0 });
 
    while (!pq.empty())
    {
        Node popedNode = pq.top();
        pq.pop();
        int curNode = popedNode.node;
        int curDistance = popedNode.distance;
 
        if (dist[curNode] < curDistance) continue;
 
        for (int i = 0; i < graph[curNode].size(); i++)
        {
            int next = graph[curNode][i].node;
            int nextDistance = graph[curNode][i].distance;
 
            if (curDistance + nextDistance < dist[next])
            {
                dist[next] = curDistance + nextDistance;
                pq.push({ next,dist[next] });
            }
        }
    }
 
    return dist[dest];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int v, e;
    int a, b, c;
    int ca, cb;
 
    cin >> v >> e;
 
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
 
    cin >> ca >> cb;
 
    int route1 = djik(1, ca) + djik(ca, cb) + djik(cb, v);
    int route2 = djik(1, cb) + djik(cb, ca) + djik(ca, v);
 
    if (route1 >= MAX_NUM || route2 >= MAX_NUM)
        cout << -1;
    else cout << min(route1, route2);
}
 

 

 

508ms가 플로이드와샬, 44ms가 다익스트라로 푼 결과이다.