문제

문제 링크

어떻게 접근할 것인가?

  • 다익스트라를 이용한다.

문제

  • 문제는 노드의 거리가 변경되면서 힙에서의 순서가 바뀌게 되는데 그걸 어떻게 처리해줄 것이냐 하는 것이다.
  • STL의 priority_queue에는 decrease_key와 같은 function을 제공하지 않는다.
  • 매번 heapify해주는 것은 시간이 너무 오래 걸린다ㅠㅠ 시간초과..ㅠㅠㅠ 그렇다면??

해결 방안

  • 힙에 업데이트된 거리의 새로운 노드를 넣어준다.
  • 그리고 모든 노드가 확인될 때까지 iteration을 반복한다.
  • 그를 위해 visited array를 생성해줬다.

처음 맞은 코드

#include <cstdio>
#include <vector>
#include <queue>
#define INF 10000000

using namespace std;

typedef struct Point{
    int v, w;
    Point(){}
    Point(int i, int j){
        v = i;
        w = j;
    }
}Point;

int V, E, K, u, v, w, n;
vector< vector< Point > > ll;
vector<int> d;
int visited[20002];

struct cmp{
    bool operator()(int a, int b){return d[a] > d[b];}
};

int main(){
    scanf("%d %d %d", &V, &E, &K);
    ll = vector< vector< Point > >(V+1);
    d = vector<int>(V+1);
    priority_queue<int, vector<int>, cmp> pq;

    for(int i = 1; i < V+1; i++) {
        d[i] = INF;
        if(i == K)d[i] = 0;
        pq.push(i);
    }
    for(int i = 0; i < E; i++){
        scanf("%d %d %d", &u, &v, &w);
        ll[u].push_back(Point(v, w));
    }
    
    while(!pq.empty()){
        u = pq.top(); pq.pop();
        if(visited[u])continue;
        for(int i = 0; i < ll[u].size(); i++){
            v = ll[u][i].v, w = ll[u][i].w;
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push(v);
            }
        }
    }
    for(int i = 1; i < d.size() ; i++){
        if(d[i] == INF) printf("INF\n");
        else printf("%d\n", d[i]);
    }
}

회고

  • 일단 나는 당연히 처음에 노드를 다 넣어야한다고 생각했는데 그렇지 않은 코드가 많았다.
  • 나도 수정해볼 여지가 있었다.
  • 그리고 다들 인풋을 신기하게 받는데 시간이 엄청나게 줄었다… 나도 써봐야하나..

회고 후 코드

#include <cstdio>
#include <vector>
#include <queue>
#define INF 10000000

using namespace std;

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

typedef struct Point{
    int v, w;
    Point(){}
    Point(int i, int j){
        v = i;
        w = j;
    }
}Point;

struct cmp {
    bool operator()(Point x, Point y) {
        return x.w > y.w;
    }
};

int V, E, K, u, v, w, n;
vector< vector< Point > > ll;

vector<int> djistra(int root){
    vector<int> d(V+1, INF);
    priority_queue<Point, vector<Point>, cmp> pq;
    d[root] = 0; 
    pq.push(Point(root, d[root]));
    while(!pq.empty()){
        u = pq.top().v, w = pq.top().w; pq.pop();
        if(w > d[u]) continue; //weight가 다른 중복이 있을 수 있기 때문에
        for(int i = 0; i < ll[u].size(); i++){
            v = ll[u][i].v, w = ll[u][i].w;
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push(Point(v, d[v]));
            }
        }
    }
    return d;
}

int main(){
    scanf("%d %d %d", &V, &E, &K);
    ll = vector< vector< Point > >(V+1);
    
    for(int i = 0; i < E; i++){
        u = readInt(), v = readInt(), w = readInt();
        ll[u].push_back(Point(v, w));
    }

    vector<int> d = djistra(K);
    
    for(int i = 1; i < d.size() ; i++){
        if(d[i] == INF) printf("INF\n");
        else printf("%d\n", d[i]);
    }
}

결과

사진

  • 10위권 안에 들었다!!ㅎㅎ 대박!

느낀점

  • 다익스트라 개꿀~ 했다가 심하게 혼났다.
  • 모든 노드를 처음에 다 넣고 시작하지 않으니까 굳이 Heapify를 다시 안해도 되었다.
  • 내가 생각하는 알고리즘과 교수님이 알려주신거가 다가 아니라는 생각이 든다.
  • 다익스트라를 다시 보게 된 계기였다.
  • 순위권안에 든거 자체가 너무 설렌다 ㅎㅎ