글 읽기 - 17%에서 틀렸어요 ㅠㅠ

uk3181 15일 전 0

혹시 왜 틀린지 반례 케이스가 있을까요? 어디서 틀렸는지 모르겠네요...

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

#define INF LLONG_MAX

using namespace std;

class Element {
public:
    vector<pair<short, int>> branches; // <노드, 비용>
};

void setGraph(vector<Element>& graph) {
    short N; // 도시의 개수
    cin >> N;
    for (short i = 0; i < N; i++)
        graph.push_back(Element());

    int M; // 버스의 개수
    cin >> M;

    for (int i = 0; i < M; i++) {
        short startNode, endNode;
        int cost;
        cin >> startNode >> endNode >> cost;

        graph[startNode - 1].branches.push_back(make_pair(endNode, cost));
    }
}

short findMinCost(vector<pair<long long, bool>>& costs) {
    short minNode = -1;
    long long minCost = INF;
    for (short i = 0; i < costs.size(); i++) {
        if (!costs[i].second && costs[i].first < minCost) {
            minCost = costs[i].first;
            minNode = i;
        }
    }
    return minNode;
}

void dijkstra(vector<Element>& graph, vector<pair<long long, bool>>& costs) {
    for (short i = 0; i < costs.size(); i++) {
        short currentNode = findMinCost(costs);
        if (currentNode == -1)
            break;

        long long currentCost = costs[currentNode].first;
        costs[currentNode].second = true;
        if (currentCost == INF)
            continue;

        // 각 정점과 인접한 정점들을 탐색
        for (short j = 0; j < graph[currentNode].branches.size(); j++) {
            short branchNode = graph[currentNode].branches[j].first;
            long long cost = (long long)currentCost + graph[currentNode].branches[j].second;

            if (cost < costs[branchNode - 1].first)
                costs[branchNode - 1].first = cost;
        }
    }
}

long long solve(vector<Element>& graph, short startNode, short endNode) {
    vector<pair<long long, bool>> costs;
    for (short i = 0; i < graph.size(); i++)
        costs.push_back(make_pair(INF, false));
    costs[startNode - 1].first = 0;

    dijkstra(graph, costs);

    return costs[endNode - 1].first;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<Element> graph;
    setGraph(graph);

    short startNode, endNode;
    cin >> startNode >> endNode;

    cout << solve(graph, startNode, endNode) << '\n';

    return 0;
}

dyepeyyt 15일 전 0

class 선언하실 때, pair<short,int>를 pair<int,int>로 바꿔보시겠어요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17%에서 틀렸어요 ㅠㅠ

uk3181 15일 전 0

dyepeyyt 15일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말