[BOJ-5719]거의최단경로

맞았다....기쁘다.......

근데 코드가 너무더럽다......

정말 모든 최단경로를 다 지워줘야하는 문제

경로를 어떻게 지울 것인지?

1. 다익스트라로 최단경로를 모두 구한다. (정방향 에지)

2. 목적지부터 다시 다익스트라를 돌리며 (반대방향 에지), 에지를 저장한다. dst-src

3. 정방향 에지 중 저장한 에지로 지워준다.

4. 다시 다익스트라를 정방향으로 src-dst 로 돌려 구한다.

/* input */
4 5
0 2
0 1 1
0 3 5
1 2 2
1 3 1
3 2 1
0 0
/* output */
-1
// 6이 아닙니다...............

#include<cstdio>
#include<functional>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
 
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
 
const int INF = 888888888;
 
VI vertex;
VI past;
VPII edge[888];
VPII back_edge[888];
VI save_edge[888];
int n,e;
 
int dijkstra(int src, int dst){
    past = VI(n+1, -1);
    vertex = VI(n+1, INF);
    vertex[src] = 0;    
    priority_queue<PII, VPII, greater<PII> > Q;
    Q.push(mp(0, src));
    while(!Q.empty()){
        int here = Q.top().second;
        int dist = Q.top().first;
        Q.pop();
        if(vertex[here] < dist) continue;
 
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            PII p = *iter;
            int there = p.first;
            int cost = p.second;
            if(vertex[there] > vertex[here] + cost){
                vertex[there] = vertex[here] + cost;
                past[there] = here;
                Q.push(mp(vertex[there], there));
            }
        }
    }
    return vertex[dst];
}
 
void delete_edge(int dst, int src){
    priority_queue<PII> Q;
    Q.push(mp(vertex[dst],dst));
 
    while(!Q.empty()){
        int here = Q.top().second;
        int dist = Q.top().first;
        Q.pop();
 
        for(auto iter = back_edge[here].begin() ; iter != back_edge[here].end() ; iter++){
            PII p = *iter;
            int there = p.first;
            int cost = p.second;
            if(vertex[there] == vertex[here] - cost){
                save_edge[there].pb(here);
                Q.push(mp(vertex[there],there));
            }
        }
    }
 
    for(int i = 0 ; i < n ; i++){
        for(auto it_2 = save_edge[i].begin() ; it_2 != save_edge[i].end() ; it_2++){
            int there2 = *it_2;
            for(auto it_1 = edge[i].begin() ; it_1 != edge[i].end() ; it_1++){
                PII p1 = *it_1;
                int there1 = p1.first;
                if(there1 == there2){
                    edge[i].erase(it_1);
                    //save_edge[i].erase(it_2);
                    break;
                }
            }
        }
    }
 
}
 
int main(){
    while(true){
        scanf("%d%d", &n, &e);    
        if(n==0 && e==0) return 0;
 
        for(int i = 0 ; i <= n ; i++){
            edge[i].clear();
            back_edge[i].clear();
            save_edge[i].clear();
        }
 
        int src, dst;
        scanf("%d%d", &src, &dst);
        for(int i = 0 ; i < e ; i++){
            int u,v,w;
            scanf("%d%d%d", &u, &v, &w);
            edge[u].pb(mp(v,w));
            back_edge[v].pb(mp(u,w));
        }
        
        int minimal = dijkstra(src,dst);
 
        delete_edge(dst, src);
 
        int ans = dijkstra(src,dst);
        if(ans == INF || minimal == INF){
            puts("-1");
        }else if(minimal < ans){
            printf("%d\n",ans);
        } 
 
    }
 
    return 0;
}