백준 5719 거의 최단 경로 혼내주기

 

 

다잌으로 모든 최단 경로를 찾고(길이가 같은 여러개의 최단 경로가 있을수도 있음) 그 경로들을 지운다음 나머지 경로들로 최단 경로를 찾으면 된다.

삽질했던 포인트:
1. 길이가 같은 여러개의 최단 경로를 생각 못함
2. pq에 거리가 같은 경우는 경로만 넣어야 하는데 중복되는 간선을 넣음 (주석으로 표시)
3. 경로를 제거할때 사이클이 있는 경우가 있어서 visited 배열로 중복 방문을 막았어야 함

공식 사이트에 있는 TC로 체크해서 답이 맞는데도 시간초과가 나와서 굉장히 헤맸다... 결국 8트만에 성공...

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

struct state {
    int from, dist; bool valid;
    state(int ff, int dd, int vv) {from = ff, dist = dd, valid = vv;}
};

bool visited[501][501];
int adj[501][501];
int n, m, src, dst;

void input() {
    cin >> src >> dst;
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj[a][b] = c;
    }
}

void dfs(int from, const vector<vector<int> >& path) {
    for(auto& to : path[from]) {
        if(visited[to][from]) continue;
        visited[to][from] = true;
        adj[to][from] = -1;
        dfs(to, path);
    }
}

int dijkstra() {
    vector<int> dist(n+1, 2e9);
    vector<vector<int> > path(n+1, vector<int>());
    priority_queue<pii> pq;
    dist[src] = 0;
    pq.push({src, 0});
    while(!pq.empty()) {
        auto [from, d] = pq.top(); pq.pop(); d *= -1;
        if(dist[from] < d) continue;
        for(int to = 0; to < n; ++to) {
            int nDist = d + adj[from][to];
            if(adj[from][to] == -1 || dist[to] < nDist) continue;
            if(dist[to] > nDist) {
                path[to].clear();
                dist[to] = nDist;
                pq.push({to, -nDist});
            }
            path[to].push_back(from);	// 중복된건 넣지 않는다
        }
    }
    // remove shortest path
    dfs(dst, path);
    return dist[dst];
}

int main() {
    fastio;
    while(cin >> n >> m) {
        if(!n && !m) break;
        memset(adj, -1, sizeof(adj));
        memset(visited, false, sizeof(visited));
        input();
    
        dijkstra();
        int ret = dijkstra();
        cout << (ret == 2e9 ? -1 : ret) << "\n";
    }
}