녹색 옷 입은 애가 젤다지? - 4485번 백준

문제

문제 난이도 : 골드 4

문제 분류 : 다익스트라

문제 리뷰

딱히.. 없지만.. memset 이거 왜 작동 잘 안하는지 모르겠다.

제대로 다시 알아보자,,

문제 소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;
vector<pair<int, int>> Edges[16000];
int Distance[16000];
void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}

void Dijkstra(int start)
{
    for (int i = 0; i < 16000; i++)
    {
        Distance[i] = 2100000000;
    }
    Distance[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,0 });

    while (!pq.empty())
    {
        pair<int, int> p = pq.top();
        pq.pop();
        int CurDist = - p.first;
        int MidDest = p.second;
        for (int i = 0; i < Edges[MidDest].size(); i++)
        {
            pair<int, int> np = Edges[MidDest][i];
            int NextDist = np.first;
            int FinalDest = np.second;
            if (Distance[FinalDest] > NextDist + CurDist)
            {
                Distance[FinalDest] = NextDist + CurDist;
                pq.push({ - Distance[FinalDest], FinalDest });
            }
        }
    }
    for (int i = 0; i < 16000; i++) {
        Edges[i].clear();
    }
}

int main()
{
    //Initialize
    Init();
    int n;
    int Count = 1;
    while (cin >> n)
    {
        if (n == 0) break;
        int Map[200][200];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp;
                cin >> tmp;
                Map[i][j] = tmp;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) {
                    Edges[i * n + j].push_back({ Map[i-1][j], (i - 1) * n + j });
                }
                if (i < n - 1) {
                    Edges[i * n + j].push_back({ Map[i + 1][j], (i + 1) * n + j });
                }
                if (j > 0) {
                    Edges[i * n + j].push_back({ Map[i][j-1], i * n + j - 1 });
                }
                if (j < n - 1) {
                    Edges[i * n + j].push_back({ Map[i][j+1], i * n + j + 1 });
                }
            }
        }

        Dijkstra(0);
        std::cout << "Problem " << Count++ << ": " << Map[0][0] + Distance[n * n - 1] << "\n";

    }
}