글 읽기 - 50% 에서 틀렸습니다가 계속 뜹니다.

girlera7 3년 전 0

지나야 하는 점 2개를 A, B라고 할때

1 -> A - > B ->n

1 ->B -> A ->n

2가지를 고려해주었고, 각각에 대해 다익스트라를 적용했는데 자꾸

50% 부근에서 틀렸다고 뜹니다.

#include <iostream>
#include<vector>
#include<queue>
#define INF 1e9

using namespace std;

vector<pair<int, int>> edge[200000];

int dijkstra(int source, int dest) {
    priority_queue<pair<int, int>> pq;
    int dist[800];
    pq.push({0, source});
    dist[source] = 0;

    fill(dist, dist + 800, INF);

    int curDist;
    int curLocation;
    int nextDist;
    int nextLocation;

    while(!pq.empty()) {
        curDist = -pq.top().first;
        curLocation = pq.top().second;

        pq.pop();

        for(auto &p: edge[curLocation]) {
            nextDist = p.first;
            nextLocation = p.second;

            if(dist[nextLocation] > nextDist + curDist) {
                dist[nextLocation] = nextDist + curDist;
                pq.push({-dist[nextLocation], nextLocation});
            }
        }

    }

    return dist[dest];

}

int main() {
    ios_base::sync_with_stdio(0);

        cin.tie(0);
    
    int v, e;
    int s, d, weight;

    cin >> v >> e;



    for(int i = 0; i < e; i++) {
        cin >> s >> d >> weight;
        edge[s - 1].push_back({weight, d - 1});
        edge[d - 1].push_back({weight, s - 1});
    }

    int r1, r2;
    cin >> r1;
    cin >> r2;
    r1 -= 1;
    r2 -= 1;

    int val;

    if(r1 == 0 && r2 == v - 1) {
        if(dijkstra(r1, r2) == INF) {
            val = -1;
        } else{
        val = dijkstra(r1, r2);
        }
    } else if(r1 == 0) {
        if(dijkstra(0, r2) == INF || dijkstra(r2, v - 1) == INF) {
            val = -1;
        } else {
            val = dijkstra(0, r2) + dijkstra(r2, v - 1);
        }
    } else if(d == v - 1) {
        if(dijkstra(0, r1) == INF || dijkstra(r1, v - 1) == INF) {
            val = -1;
        } else {
            val = dijkstra(0, r1) + dijkstra(r1, v - 1);
        }
    
    } else{
        int min1;
        int min2;
        

        if(dijkstra(0, r1) == INF || dijkstra(r1, r2) == INF || dijkstra(r2, v - 1) == INF) {
            val = -1;
        } else if(dijkstra(0, r2) == INF || dijkstra(r2, r1) == INF || dijkstra(r1, v - 1) == INF) {
            val = -1;
        } 
        else {
            min1 = dijkstra(0, r1) + dijkstra(r1, r2) + dijkstra(r2, v - 1);
            min2 = dijkstra(0, r2) + dijkstra(r2, r1) + dijkstra(r1, v - 1);
            if (min1 <= min2) {
                val = min1;
            } else {
                val = min2;
            }
            
            if(val >= INF) {
                val = -1;
            }
        }
    }
        

    cout << val;

    return 0;
}

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

문제

문제

출처

ICPC

50% 에서 틀렸습니다가 계속 뜹니다.

girlera7 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말