글 읽기 - 반례가 혹시 있을까요?

kbp0237 4년 전 0

다 익스트라, 플로이드류의 최단경로 문제를 연습하는 중이라 풀고있습니다.

채점에서 100% 찍고 틀렸습니다가 떠서 더 머리가 아프네요

심지어 질문에 있는 반례도 정답이 나옵니다.

뭐가 문제일까요 ㅠㅠ

다 익스트라를 익숙치가 않아서 두번 돌리는게 좀 불편하실지도 모르지만...ㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define INF 1000000000
typedef pair<int, int> P;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    vector<P> adj[110]; // (이어진 정점 번호, 거리)
    int V, M;
    
    cin >> V >> M;
    
    for (int i = 0; i < M; i++) // 간선 정보 입력
    {
        int a, b, c;
        
        cin >> a >> b >> c;
        adj[a].push_back(P(b, c));
        adj[b].push_back(P(a, c));
    }
    
    int jihun, sungha;
    
    cin >> jihun >> sungha;
    
    int distj[110]; // 지헌으로부터 거리 저장
    int dists[110]; // 성화로부터 거리 저장
    int sum[110]; // 성화와 지헌으로부터 거리 각각을 합한 값 저장
    
    fill(distj, distj + 110, INF);
    fill(dists, dists + 110, INF);
    fill(sum, sum + 110, INF);
    
    bool visiteds[110] = {0,};
    bool visitedj[110] = {0,};
    priority_queue<P, vector<P>, greater<P>> JPQ;
    priority_queue<P, vector<P>, greater<P>> SPQ;
    
    distj[jihun] = 0;
    JPQ.push(P(0, jihun));
    while (!JPQ.empty())
    {
        int curr;
        
        do {
            curr = JPQ.top().second;
            JPQ.pop();
        } while (!JPQ.empty() && visitedj[curr]);
        
        if (visitedj[curr]) break;
        
        visitedj[curr] = true;
        
        for (auto &p : adj[curr])
        {
            int next = p.first, d = p.second;
            
            if (distj[next] > distj[curr] + d)
            {
                distj[next] = distj[curr] + d;
                JPQ.push(P(distj[next], next));
            }
        }
    }
    
    dists[sungha] = 0;
    SPQ.push(P(0, sungha));
    while (!SPQ.empty())
    {
        int curr;
        
        do {
            curr = SPQ.top().second;
            SPQ.pop();
        } while (!SPQ.empty() && visiteds[curr]);
        
        if (visiteds[curr]) break;
        
        visiteds[curr] = true;
        
        for (auto &p : adj[curr])
        {
            int next = p.first, d = p.second;
            
            if (dists[next] > dists[curr] + d)
            {
                dists[next] = dists[curr] + d;
                SPQ.push(P(dists[next], next));
            }
        }
    }
    
    int tmp = 1100000000;
    vector<P> save;
    
    for (int i = 1; i <= V; i++)
    {
        if (dists[i] == 0)
            dists[i] = INF;
        
        if (distj[i] == 0)
            distj[i] = INF;

        sum[i] = dists[i] + distj[i];
        
        if (sum[i] < tmp)
        {
            save.clear();
            save.push_back(P(sum[i], i));
            tmp = sum[i];
        } else if (sum[i] == tmp)
        {
            save.push_back(P(sum[i], i));
        }
    }
    
    int ans = 200;
    int tmpdist = 200000;
    

    for (int i = 0; i < save.size(); i++)
    {
        if (distj[save[i].second] <= dists[save[i].second]) // 지헌이가 덜 걸리는 경우
        {
            if (tmpdist > distj[save[i].second])
            {
                tmpdist = distj[save[i].second];
                ans = save[i].second;
            } else if (tmpdist == distj[save[i].second])
            {
                if (ans > save[i].second)
                {
                    ans = save[i].second;
                }
            }
        }
    }
    
    if (ans >= 200)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
    
}

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

문제

문제

출처

ICPC

반례가 혹시 있을까요?

kbp0237 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말