Vic_cinth
1916_최소비용 구하기

  20 Nov 2019


Problem

Image

Concept & Idea

다익스트라 문제였고, 프림 알고리즘을 이용하여 해결하였다.
메모리 초과는 dp[1][1001] 이 배열만을 선언함으로 해결할 수 있었다.

  1. 우선 이 문제는 단일 방향의 간선이라는 점도 중요하고, 같은 경로지만 여러대의 버스가 존재할 수 있다. 역시 질문을 잘 읽는 것이 중요하다..
  2. 원래 메모리 초과가 났을 때, 배열을 2차원으로 선언했었다. 하지만 시작점은 한 곳이고,, 마지막 도착지까지 가려면 반드시 start지점을 거친 값에 더해주어야 하기 때문에, 일차원 배열으로 해결할 수 있다.

Code

#include <iostream>
#include <queue>
using namespace std;
struct node{
    int x,y,z;
    bool operator()(node a,node b){
        return a.z>b.z;
    }
};
priority_queue<node,vector<node>,node> pqu;
vector<pair<int, int>> vec[1001];
int n,m,dp[1][1001];
int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++) {
        node temp;
        cin>>temp.x>>temp.y>>temp.z;
        vec[temp.x].push_back({temp.y,temp.z});
    }
    int st,en;
    cin>>st>>en;
    for(int i=1; i<=n; i++) {
        if(st!=i)
            dp[0][i]=100000001;
    }
    for(int i=0; i<vec[st].size(); i++) {
        node t;
        t.x=st; t.y=vec[st][i].first; t.z=vec[st][i].second;
        pqu.push(t);
    }
    while(!pqu.empty()) {
        node tem = pqu.top();
        pqu.pop();
        if(dp[0][tem.y]>dp[0][tem.x]+tem.z) {
            dp[0][tem.y]=dp[0][tem.x]+tem.z;
            for(int i=0; i<vec[tem.y].size(); i++) {
                node t;
                t.x=tem.y; t.y=vec[tem.y][i].first; t.z=vec[tem.y][i].second;
                pqu.push(t);
            }
        }
    }
    cout<<dp[0][en]<<endl;
}

Fealing

시간초과, 메모리 초과, 틀렸습니다로 엄청 고생한 문제이다.
아마 더 일찍 해결할 수 있음에도,, 메모리초과때문에 기분나빠서 나중에 푼 문제다.
필요없는 배열은 없애고 효율적으로 짜기위해 노력한 문제다.. 내 50퍼대 정답율을 잃어버리게 한 문제이기도 하다..

Check out this code in Victoria’s Gist. Please Comment my code in this link.

...