다익스트라

전처리

static class Pair implements Comparable<Pair>
{
    int v, w;

    Pair () {}
    Pair (int v, int w) { this.v = v; this.w = w; }

    public int compareTo(Pair o) {
        return this.w - o.w;
    }
}


ArrayList<Pair>[] G = new ArrayList[N+1];


for (int i=1; i<=N; i++)
    G[i] = new ArrayList<>();


for (int i=0; i<M; i++)
{
    st = new StringTokenizer(input.readLine());

    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    int w = Integer.parseInt(st.nextToken());

    G[u].add( new Pair(v, w) );
}

 

 

 

 

다익스트라 (priority queue)

static int[] Dijkstra (ArrayList<Pair>[] G, int N, int start, int INF)
{
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    boolean[] isVisited = new boolean[N+1];
    int[] dist = new int[N+1];

    for (int i=1; i<=N; i++)
        dist[i] = INF;

    dist[start] = 0;
    pq.add( new Pair(start, 0) );

    while ( !pq.isEmpty() )
    {
        int u = pq.poll().v;

        if ( isVisited[u] == true )
            continue;

        isVisited[u] = true;

        for (int i=0; i<G[u].size(); i++)
        {
            int v = G[u].get(i).v;
            int w = G[u].get(i).w;

            if ( dist[u] + w < dist[v] )
            {
                dist[v] = dist[u] + w;
                pq.add(new Pair(v, dist[v]));
            }
        }
    }

    return dist;
}