글 읽기 - 오버플로우 이외의 엣지케이스

se030 2년 전 0

게시판 보고 long long int, INF값 설정 관련된 부분 모두 체크했는데 계속 100%에서 틀렸습니다가 뜨네요..

로직은 다른 분들이랑 같은데 ㅠㅠ 이 문제에서 또 고려해야할 엣지케이스가 있을까요?

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 500000000
using namespace std;

int N, E, a, b, c, v1, v2;
long long int dist[801], v1first = 0, v2first = 0;
vector<pair<int, int>> edge[801];   // edge[k]: k에 연결된 엣지 정보 {to, cost}
priority_queue<pair<long long int, int>,
    vector<pair<long long int, int>>,
    greater<pair<long long int, int>>> Q;
void init(int n){
    for (int i=1; i<801; i++)
        dist[i] = INF;
    dist[n] = 0;
    Q.push({dist[n], n});   // Q: 현재 dist set {dist, current}
}
void dijk(int n) {
    init(n);
    while (Q.size()) {
        pair<long long int, int> cur = Q.top();
        Q.pop();
        for (int i=0; i<edge[cur.second].size(); i++) {
            pair<int, int> e = edge[cur.second][i]; // to, cost
            if (cur.first + e.second < dist[e.first]) {
                dist[e.first] = cur.first + e.second;
                Q.push({dist[e.first], e.first});
            }
        }
    }
}
void sol() {
    dijk(1);
    v1first += dist[v1];
    v2first += dist[v2];
    dijk(v1);
    v1first += dist[v2];
    v2first += dist[v2];
    dijk(N);
    v1first += dist[v2];
    v2first += dist[v1];
    long long int res = min(v1first, v2first);
    printf("%lld\n", INF < res? -1:res);
}
int main() {
    scanf("%d %d", &N, &E);
    for (int i=0; i<E; i++) {
        scanf("%d %d %d", &a, &b, &c);
        edge[a].push_back({b,c});
        edge[b].push_back({a,c});
    }
    scanf("%d %d", &v1, &v2);
    sol();
    return 0;
}

Green55 2년 전 2

반례입니다.

2 0
1 2

ans : -1

se030 2년 전 0

와 너무 답답했는데...

확인해봤던 반례인데 수정하다가 등호를 빠뜨렸나봐요 감사합니다 ㅠㅠ!!!!

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

문제

문제

출처

ICPC

오버플로우 이외의 엣지케이스

se030 2년 전 0

Green55 2년 전 2

se030 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말