글 읽기 - 형님들 틀린 이유를 못찾겠습니다.

wkdalstn1004 5년 전 0

시야가 점점 좁아져서 이제 뭘 바꿔야되는지 보이지가 않습니다.

using System;
using System.Collections.Generic;

namespace MinDistance
{
    class Program
    {
        static int[] min;
        static bool[] visit;
        static Graph g;
        static void Main(string[] args)
        {
            g = new Graph();
            string[] str = Console.ReadLine().Split(' ');
            int vCount = int.Parse(str[0]);
            int eCount = int.Parse(str[1]);
            int start = int.Parse(Console.ReadLine());

            min = new int[vCount];
            visit = new bool[vCount];

            

            for(int i = 0; i < vCount; i++) 
            {
                InsertVerticle();
                min[i] = int.MaxValue;
                visit[i] = false;
            }
            for (int i = 0; i < eCount; i++) 
            {
                str = Console.ReadLine().Split(' ');
                InsertEdge(int.Parse(str[0]) - 1, int.Parse(str[1]) - 1, int.Parse(str[2]));
            }
            str = new string[1];

            MinDistance(start - 1, vCount - 1, vCount);
            for (int i = 0; i < vCount; i++)
            {
                if (min[i] == int.MaxValue) Console.Write("INF\n");
                else Console.Write(min[i] + "\n");
            }
        }

        static void MinDistance(int start, int def, int length)
        {
            Queue<int> q = new Queue<int>();
            Node n;
            min[start] = 0;
            visit[start] = true;
            q.Enqueue(start);
            while (q.Count >0)
            {
                start = q.Dequeue();
                n = g.list[start];
                while (n != null)
                {
                    if (!visit[n.direction])
                    {
                        if (!q.Contains(n.direction)) q.Enqueue(n.direction);
                        visit[n.direction] = true;
                    }
                    if (min[n.direction] > min[start] + n.dist)
                    {
                        min[n.direction] = min[start] + n.dist;
                    }
                    n = n.link;
                }
                
            }
        }

        static void InsertEdge(int s, int e, int w)
        {
            
            Node node = new Node();
            node.direction = e;
            node.link = g.list[s];
            node.dist = w;
            g.list[s] = node;

            Node node1 = new Node();
            node1.direction = s;
            node1.link = g.list[e];
            node1.dist = w;
            g.list[e] = node1;
            
        }

        static void InsertVerticle()
        {
            if (g.list == null) g.list = new List<Node>();
            g.list.Add(null);
        }
    }
    public class Node
    {
        public Node link;
        public int direction;
        public int dist;
    }

    public class Graph
    {
        public List<Node> list;
        
    }
}

chogahui05 5년 전 0

가중치가 다른 최단거리 문제를 단순히 Queue로 이용해서 풀 수 있을까요?

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

문제

문제

출처

ICPC

형님들 틀린 이유를 못찾겠습니다.

wkdalstn1004 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말