[C++] 백준 1504 특정한 최단 경로

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
 
int N = 0;
std::vector<std::pair<int, int>> vecPair[801];
int visit[801] = {};
int iMin = 100000000;
 
void Dijkstra(int iNow)
{
    for (int i = 1; i <= N; i++)
    {
        visit[i] = 100000000;
    }
 
    visit[iNow] = 0;
 
    std::priority_queue<std::pair<int, int>, 
        std::vector<std::pair<int, int>>, 
        std::greater<std::pair<int, int>>> pri_que = {};
 
    pri_que.push({ 0, iNow });
 
    while (!pri_que.empty()) 
    {
        int iDist = pri_que.top().first;
        int iX = pri_que.top().second;
        pri_que.pop();
 
        for (int i = 0; i < vecPair[iX].size(); ++i)
        {
            int iNextX = vecPair[iX][i].first;
            int iNextDist = vecPair[iX][i].second;
 
            if (visit[iNextX] > iDist + iNextDist)
            {
                visit[iNextX] = iDist + iNextDist;
                pri_que.push({ visit[iNextX],iNextX });
            }
        }
    }
}
 
int main()
{
    int E = 0;
    std::cin >> N >> E;
 
    int iStart = 0;
    int iEnd = 0;
    int iDist = 0;
 
    for (int i = 0; i < E; ++i)
    {
        std::cin >> iStart >> iEnd >> iDist;
 
        vecPair[iStart].push_back({ iEnd, iDist });
        vecPair[iEnd].push_back({ iStart, iDist });
    }
 
    std::cin >> iStart >> iEnd;
 
    Dijkstra(1);
    int iOneStart = visit[iStart];
    int iOneEnd = visit[iEnd];
 
    Dijkstra(iStart);
    int iStartEnd = visit[iEnd];
    int iStartN = visit[N];
 
    Dijkstra(iEnd);
    int iEndN = visit[N];
 
 
    if (iStartEnd == 100000000 || 
        iOneStart == 100000000 || 
        iOneEnd == 100000000 ||
        iStartN == 100000000)
    {
        std::cout << -1;
    }
 
    else
    {
        std::cout << std::min(iOneStart + iStartEnd + iEndN, iOneEnd + iStartEnd + iStartN);
    }
 
    return 0;
}
 

처음에는 BFS로 풀 수 있을 줄 알았습니다.

시작 -> 2 -> 3 -> N으로 풀면 될까 싶었는데 시간초과...

다익스트라자를 이용해서 최단거리 경로를 구해서 풀었습니다.

한 점에서 어떠한 위치에 얼마나 가볍게 갈 수 있는가에 대한 값이 가장 중요합니다.