글 읽기 - 우선순위 큐가 없어서 간단하게 list로 구현했는데 틀렸다고 나옵니다 ㅠㅜ

sangjin256 4년 전 0

c#에 우선순위 큐가 없어서 간단하게 list에 넣고 바로 sort로 정렬해주었습니다.

예제문제는 답 나오는데 틀렸다고 뜨네요 왜그런건가요 ㅠㅜ

using System;
using System.IO;
using System.Collections.Generic;
public class Lecture 
{
    // 인접 리스트의 형태로 그래프를 저장해준다.
    static List<(int,int)>[] adj;
    // c#에는 우선순위 큐가 없으므로 list의 sort로 그 일을 대신한다. 
	static List<(int,int)> asc = new List<(int,int)>();
    //거리를 담아줄 배열
    static int[] distance;
    //처리했는지를 체크하는 배열
    static bool[] processed;
	public static void Main(string[] args) {
        //정점의 개수 arr[0]와 간선의 개수 arr[1]
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), s => int.Parse(s));
        //시작 노드
        int start = int.Parse(Console.ReadLine());

        //배열들 초기화
        adj = new List<(int,int)>[arr[0]+1];
        for(int i = 0; i < arr[0]+1; i++){
            adj[i] = new List<(int,int)>();
        }
        distance = new int[arr[0]+1];
        processed = new bool[arr[0]+1];

        //셋째줄부터는 (a,b,w)를 받는다.
        for(int i = 0; i < arr[1]; i++){
            int[] tmp = Array.ConvertAll(Console.ReadLine().Split(' '), s => int.Parse(s));
            adj[tmp[0]].Add((tmp[1],tmp[2]));
        }

        for(int i = 1; i < arr[0]+1; i++){
            //w가 10 이하의 자연수라고 명시되어있으므로 그것보다 큰 11로 만들어준다.
            distance[i] = 11;
        }
        //시작노드에서 시작노드로의 거리는 0
        distance[start] = 0;
        asc.Add((0,start));
        while(asc.Count != 0){
            int a = asc[0].Item2; asc.RemoveAt(0);
            if(processed[a]) continue;
            processed[a] = true;
            foreach(var u in adj[a]){
                int b = u.Item1; int w = u.Item2;
                if(distance[a] + w < distance[b]){
                    distance[b] = distance[a] + w;
                    asc.Add((distance[b],b));
                    //sort 순서 헷갈리지 말기
                    asc.Sort((x,y) => x.Item1.CompareTo(y.Item1));
                }
            }
        }
        
        for(int i = 1; i < arr[0] + 1; i++){
            //경로가 없다는 것은 거리가 한번도 줄어들지 않았다는 뜻이므로 11이면 INF로 표시
            if(distance[i] == 11){
                Console.WriteLine("INF");
            }
            else{
                Console.WriteLine(distance[i]);
            }
        }
    }
}

djm03178 4년 전 0

https://www.acmicpc.net/board/...

sangjin256 4년 전 0

!! 감사합니다 틀렸습니다 문제는 해결되었습니다!!

근데 이번엔 시간초과네요 좀더 살펴보겠습니다 ㅠㅜ

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

문제

문제

출처

ICPC

우선순위 큐가 없어서 간단하게 list로 구현했는데 틀렸다고 나옵니다 ㅠㅜ

sangjin256 4년 전 0

djm03178 4년 전 0

sangjin256 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말