[BOJ-1916]최소비용구하기

이전에 최단경로 문제랑 같은 문제구나 생각하고 다익스트라 알고리즘을 코드로 작성하면 되겠다 싶었다.

근데 계속 18% 에서 WA을 받아서 

생각해보니 제대로 이해를 하고 코드를 짠 게 아니구나 ;;;;;;;;;

라는 생각이 들어서 

이전에 작성한 최단경로 문제 코드를 제출해봤는데도 틀렸다 

결론은 제대로 이해를 못했다. 

그래서 최단경로 부터 다시 풀어서 맞추긴 했는데...

우선순위 큐에 나는 간선들을 모두 때려 박는다고 생각했었다. 그게 아니었다... 

정점을 넣고 정점이 최소값으로 갱신 될 때만 때려박아야 했는데

이전 코드에서는 visited는 왜 만들었으며... 그 의도를 생각할 수 없었다.

아니 왜 이전에 작성한 최단경로 코드가 맞았는지? 거기서 부터 의심이 됐었는데

결론은 그냥 잘못작성한 걸 어거지로 맞춘거다 ... ㅋ...ㅋ....

간선을 넣는게 아니라, 갱신된 정점을 넣는거다.. 

정점이 갱신되면! 다시 최단경로가 갱신될 수 있으므로...!

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<functional>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
 
typedef long long LLD;
typedef vector<LLD> VLL;
typedef pair<LLD, LLD> PLL;
typedef vector<PLL> VPLL;
typedef pair<LLD, PLL> PLPLL;
typedef vector<bool> VB;
const LLD INF = 9999999999;
VPLL edge[22222];
VLL vertex;
int main(){
    int n,m; scanf("%d%d", &n, &m);
    
    vertex = VLL(n+1, INF);
    
    for(int i = 0 ; i < m ; i++){
        LLD u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        edge[u].pb(mp(w,v));
    }
    int s,e; scanf("%d%d", &s, &e);
    priority_queue<PLL, VPLL, greater<PLL> > Q;
    vertex[s] = 0;
    Q.push(mp(0,s));
    
    while(!Q.empty()){
        PLL h = Q.top(); Q.pop();
        LLD here = h.second;
        LLD cost = h.first;
        
        if(vertex[here] < cost) continue;
 
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            PLL p = *iter;
            LLD there = p.second;
            LLD t_cost = cost + p.first;
            if(vertex[there] > t_cost){
                vertex[there] = t_cost;
                Q.push(mp(t_cost, there));
            }
        }
    }
 
    printf("%lld",vertex[e]);
    return 0;
}