글 읽기 - 코드의 시간복잡도 계산이 어렵네요..

skydreamer21 2년 전 0

다익스트라 원리를 생각해봤을 때..

M : 비용 제한

K : 항공 노선 수

이면

O( MK log(MK) )

이렇게 되려나요? 맞는것 같기도 하고 아닌것 같기도 하고ㅠㅠ

고수님들의 확인을 받고 싶습니다 :)

import java.io.*;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static WeightGraph31 g;
    static int[][] time;
    static int N,M;
    final static int INF = Integer.MAX_VALUE;


    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        int K;
        int from, to, c, t;

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            g = new WeightGraph31(N);
            time = new int[N + 1][M + 1];
            for (int i=1;i<=N;i++) Arrays.fill(time[i],INF);

            while (K-- > 0) {
                st = new StringTokenizer(br.readLine());
                from = Integer.parseInt(st.nextToken());
                to = Integer.parseInt(st.nextToken());
                c = Integer.parseInt(st.nextToken());
                t = Integer.parseInt(st.nextToken());
                g.addEdge(from, new Air1(to,c,t));
            }
            dijkstra();
            sb.append((time[N][M]==INF) ? "Poor KCM" : time[N][M]).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static void dijkstra() {
        PriorityQueue<Air1> pq = new PriorityQueue<>();
        pq.add(new Air1(1,0,0));
        Air1 now;
        int temp_cost;
        int temp_time;

        while (!pq.isEmpty()) {
            now = pq.poll();
            if (now.to == N) break;
            if (now.cost>=M) continue;

            for (Air1 air : g.adjList[now.to]) {
                temp_cost = now.cost + air.cost;
                if (temp_cost>M) continue;
                temp_time = now.time + air.time;
                if (temp_time<time[air.to][temp_cost]) {
                    for (int i=temp_cost;i<=M;i++) {
                        if (temp_time<time[air.to][i]) time[air.to][i] = temp_time;
                        else break;
                    }
                    pq.add(new Air1(air.to,temp_cost,temp_time));
                }
            }
        }
    }
}

class Air1 implements Comparable<Air1>{
    int to, time, cost;

    public Air1 (int to, int cost, int time) {
        this.to = to;
        this.cost = cost;
        this.time = time;
    }

    @Override
    public int compareTo (Air1 V) {
        return (this.time==V.time) ? this.cost-V.cost : this.time - V.time;
    }
}

class WeightGraph31 {
    int size;
    public ArrayList<Air1>[] adjList;

    public WeightGraph31 (int size) {
        this.size = size;
        adjList = new ArrayList[size+1];
        for (int i=1;i<=size;i++) adjList[i] = new ArrayList<>();
    }

    public void addEdge (int v1, Air1 v2) {
        adjList[v1].add(v2);
    }
}

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

문제

문제

출처

ICPC

코드의 시간복잡도 계산이 어렵네요..

skydreamer21 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말