글 읽기 - 66% 틀렸습니다 - 해결해주실 분을 구합니다

unks96 1년 전 0

맞왜틀.. 이겠지만 스스로 로직상 오류를 찾지 못하여 질문드립니다.

66%에서 틀렸습니다가 나오는데, 문제점을 찾아주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

int N, M;
int S, D;
std::vector<int> adjlist[500];
int adjmat[500][500];
struct pt
{
    int v, cost;
};
struct comp
{
    bool operator()(pt a, pt b)
    {
        return a.cost > b.cost;
    }
};
std::priority_queue<pt, std::vector<pt>, comp> pq;
int visited[500];
std::vector<int> route[500];
std::queue<int> q;

int input()
{
    std::cin >> N >> M;
    if (N == 0 && M == 0) return 0;
    std::cin >> S >> D;
    for (int i = 0; i < M; i++)
    {
        int U, V, P;
        std::cin >> U >> V >> P;
        adjlist[U].push_back(V);
        adjmat[U][V] = P;
    }
    return 1;
}

void init()
{
    for (int i = 0; i < N; i++)
    {
        adjlist[i].clear();
        route[i].clear();
    }
    
    std::fill(&adjmat[0][0], &adjmat[0][0] + sizeof(adjmat) / sizeof(int), 0);
}

void find_shortest_path()
{
    std::fill(visited, visited + N, 0x7fffffff);
    
    pq = {};
    pq.push({S, 0});
    visited[S] = 0;
    
    while (!pq.empty())
    {
        pt data = pq.top(); pq.pop();
        
        for (int nv : adjlist[data.v])
        {
            pt ndata;
            ndata.v = nv;
            ndata.cost = data.cost + adjmat[data.v][ndata.v];
            
            if (ndata.cost > visited[ndata.v]) continue;
            
            if (ndata.cost < visited[ndata.v])
            {
                route[ndata.v].clear();
                pq.push(ndata);
                visited[ndata.v] = ndata.cost;
            }
            
            route[ndata.v].push_back(data.v);
        }
    }
}

void delete_edge()
{
    std::fill(visited, visited + N, 0);
    
    q.push(D);
    visited[D] = 1;
    
    while (!q.empty())
    {
        int nv = q.front(); q.pop();
        
        for (int v : route[nv])
        {
            if (visited[v]) continue;
            
            adjmat[v][nv] = 0;
            q.push(v);
            if (v != 0) visited[v] = 1;
        }
    }
}

int find_second_shortest_path()
{
    std::fill(visited, visited + N, 0x7fffffff);
    
    pq = {};
    pq.push({S, 0});
    visited[S] = 0;
    
    while (!pq.empty())
    {
        pt data = pq.top(); pq.pop();
        if (data.v == D) return data.cost;
        
        for (int nv : adjlist[data.v])
        {
            if (adjmat[data.v][nv] == 0) continue;
            
            pt ndata;
            ndata.v = nv;
            ndata.cost = data.cost + adjmat[data.v][ndata.v];
            
            if (ndata.cost >= visited[ndata.v]) continue;
            
            pq.push(ndata);
            visited[ndata.v] = ndata.cost;
        }
    }
    
    return -1;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    
    for (;;)
    {
        init();
        int con = input();
        if (!con) return 0;
        find_shortest_path();
        delete_edge();
        std::cout << find_second_shortest_path() << "\n";
    }
    
    return 0;
}

kwakws0627 1년 전 4

안녕하세요, 반례 드릴게요

코드 어느부분 고치면 되는지 천천히 생각해보세요

// input
10
7
1 1
2 1
2 1
3 3
7 3
4 2
5 2
7 2
6 1
7 4

// ans
-1

// wrong
9

unks96 1년 전 1

덕분에 해결했습니다. 정말 감사합니다!!

atg0614 3달 전 1

kwaksk0627 님은 앞으로 하시는 일 모두 잘되시길 바랄게요.

덕분에 5시간만에 해결했습니다

외쳐 갓원석!!!!!

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

문제

문제

출처

ICPC

66% 틀렸습니다 - 해결해주실 분을 구합니다

unks96 1년 전 0

kwakws0627 1년 전 4

unks96 1년 전 1

atg0614 3달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말