글 읽기 - SPFA 53% 틀렸습니다.

suby00 1년 전 1

안녕하세요 코린이입니다.

SPFA알고리즘으로 풀고있는데 반례를 찾아보았으나 제가 찾아본 반례들은 전부 통과됐습니다.

테스트코드들은 다 통과하지만 왜 53%에서 통과를 못하는건지 고수분들 알려주시면 감사하겠습니다 ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Pair<T,U> implements Comparable<Pair<T,U>> {
    private T first;
    private U second;

    Pair(T first, U second) {
        this.first = first;
        this.second = second;
    }

    public T getFirst() {
        return first;
    }

    public U getSecond() {
        return second;
    }

    @Override
    public int compareTo(Pair<T, U> o) {
        return (int) this.first - (int)o.first;
    }
}

public class Main {
    static int N;
    static int M;
    static List<List<Pair>> adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>();
        for(int i = 0 ; i<= N;i++){
            adj.add(new ArrayList<>());
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            //first cost second endvertax
            adj.get(start).add(new Pair(cost, end));
        }

        long[] dist =spfa(1);
        if (dist!= null)
        for(int i = 2; i <= N ; i++){
            System.out.println(dist[i]);
        }
    }
    public static long[] spfa(int start){
        boolean[] inq = new boolean[N+1];
        long[] dist = new long[N+1];
        Arrays.fill(dist,Long.MAX_VALUE);
        int[] visited = new int[N+1];
        Queue<Integer> q = new LinkedList<>();
        dist[start] = 0;
        q.offer(start);
        inq[start] = true;
        visited[start] = 1;

        while (!q.isEmpty()) {
            int here = q.peek(); q.poll();
            inq[here] = false;
            for(Pair i : adj.get(here)){
                int there = (int) i.getSecond();
                int thereCost = (int) i.getFirst();
                if(dist[there] > dist[here] + thereCost){
                    dist[there] = dist[here] + thereCost;
                    if(!inq[there]){
                        visited[there]++;
                        if(visited[there] >= N ){
                            System.out.println(-1);
                            return null;
                        }
                        q.offer(there);
                        inq[there] = true;
                    }
                }
            }
        }
        for(int i = 2; i <=3; i++){
            dist[i] =dist[i] == Long.MAX_VALUE ? -1 :dist[i];
        }

        return dist;

    }
}

suby00 1년 전 0

92번라인 for문 범위를 잘못설정했습니다. 해결됐습니다 !..

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

문제

문제

출처

ICPC

SPFA 53% 틀렸습니다.

suby00 1년 전 1

suby00 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말