백준 16118번 달빛 여우

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring> //memset
using namespace std;
const int MAX = 4000 + 2;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef long long ll;
const ll INF = 4000LL * 100000 * 10 + 1;
int N, M;
ll dist[MAX];
ll Foxdist[MAX][2];
vector<pli > adj[MAX];
bool visited[MAX];
void dijkstra() {
    fill(dist, dist + MAX, INF);
    priority_queue<pli, vector<pli>, greater<pli> > pq;
    pq.push({ 0,1 });
    dist[1] = 0;
    while (!pq.empty()) {
        ll cost = pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if (dist[here] != cost) continue;
        for (auto &p : adj[here]) {
            int there = p.second;
            ll new_cost = p.first + cost;
            if (dist[there] > new_cost) {
                dist[there] = new_cost;
                pq.push({ new_cost,there });
            }
        }
    }
}
void dijkstra2() {
    fill(&Foxdist[0][0], &Foxdist[MAX - 1][1] + 1, INF);
    Foxdist[1][0] = 0;
    priority_queue<pair<pli, int >, vector<pair< pli, int> >, greater<pair<pli, int > > > pq;
    pq.push({ { 0,1 }, 0 });
 
    while (!pq.empty()) {
        ll cost = pq.top().first.first;
        int here = pq.top().first.second;
        bool mult = pq.top().second;
        pq.pop();
        if (cost > Foxdist[here][mult]) continue;
 
        if (mult) {
            for (auto &there : adj[here]) {
                ll newCost = cost + there.first * 2;
                if (Foxdist[there.second][0] > newCost) {
                    pq.push({ {newCost, there.second},0 });
                    Foxdist[there.second][0] = newCost;
                }
            }
        }
 
        else {
            for (auto &there : adj[here]) {
                ll newCost = cost + there.first / 2;
                if (Foxdist[there.second][1] > newCost) {
                    pq.push({ {newCost, there.second},1 });
                    Foxdist[there.second][1] = newCost;
                }
            }
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        ll d;
        cin >> a >> b >> d;
        adj[a].push_back({ d*2,b });
        adj[b].push_back({ d*2,a });
    }
    dijkstra();
    dijkstra2();
    int cnt = 0;
 
    for (int i = 2; i <= N; i++) {
        if (dist[i] < min(Foxdist[i][0], Foxdist[i][1]))
            cnt++;
    }
    cout << cnt << endl;
 
    return 0;
}

출처:https://www.acmicpc.net/problem/16118

INF값을 long long으로 잡지 않고 int로 해서 런타임 에러가 났었네요.

cost가 long long까지 가는 것을 주의해주어야 합니다.

그리고 멍청하게 계속 우선순위 큐를 쓰는데 cost값을 앞으로 보내주지 않고 풀었네요 ㅋㅋㅋ

정말 주의해야겠습니다.