백준 5719 거의최단경로 C++

문제

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

5719번: 거의 최단 경로

 

코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;

int n, m, s, d, u, v, weight, dist[500], adj[500][500];

void dijkstra()
{
    fill(dist, dist + 500, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, s });
    dist[s] = 0;

    while (pq.size())
    {
        int curDist = pq.top().first;
        int curVertex = pq.top().second;
        pq.pop();

        if (dist[curVertex] != curDist)
            continue;

        for(int i = 0; i < n; i++)
        {
            //현재 정점에서 다음 정점으로 가는 가중치가 -1 == 최단거리인 간선을 -1로 갱신
            int nextDist = adj[curVertex][i];
            if(nextDist == -1)
                continue;
            
            if(dist[i] > dist[curVertex] + nextDist)
            {
                dist[i] = dist[curVertex] + nextDist;
                pq.push({dist[i], i});
            }
        }
    }
}

void deleteEdge()
{
    queue<int> q;
    q.push(d);

    while(q.size())
    {
        int curVertex = q.front();
        q.pop();

        for(int i = 0; i < n; i++)
        {
            if((dist[curVertex] == dist[i] + adj[i][curVertex]) && adj[i][curVertex] != -1)
            {
                adj[i][curVertex] = -1;
                q.push(i);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (true)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;

        fill(&adj[0][0], &adj[0][0] + 500 * 500, -1);

        cin >> s >> d;
        for (int i = 0; i < m; i++)
        {
            cin >> u >> v >> weight;
            adj[u][v] = weight;
        }

        dijkstra();
        deleteEdge();
        dijkstra();

        cout << (dist[d] == INF ? -1 : dist[d]) << '\n';
    }

    return 0;
}