글 읽기 - 제 실력으론 시간초과가 넘기기가 힘드네요 도와주세요

irnd04 5년 전 0

제 실력으론 시간초과가 넘기기가 힘드네요 도와주세요

dist[n][m] -> 1번 부터 n번까지의 m의 머니로 이동한 최소경로입니다.

제 생각엔 테스트케이스가 계속되면서 visit배열 초기화 및 adj배열 초기화 그리고 마지막 모든 금액을 순회하면서 최소경로를 찾는 부분에서 시간초과가 나는것 같은데요.

도와주셨음 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node {
	int v;
	int m;
	int d;
	public Node(int v, int m, int d) {
		this.v = v;
		this.m = m;
		this.d = d;
	}
}
public class Main {
	
	static int n, m, k;
	static int u, v, c, d;
	static final int INF = Integer.MAX_VALUE;
	static int[][] dist = new int [102][10002];
	static boolean[][] visit;
	static LinkedList<Node>[] adj = new LinkedList[102];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int res;
		
		int T = Integer.parseInt(br.readLine());
		
		while (T-- > 0) {
			
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			
			for (int i = 1; i <= n; i++) {
				adj[i] = new LinkedList<>();
			}
			
			visit = new boolean[n + 1][m + 1];
			
			for (int i = 0; i < k; i++) {
				st = new StringTokenizer(br.readLine());
				u = Integer.parseInt(st.nextToken());
				v = Integer.parseInt(st.nextToken());
				c = Integer.parseInt(st.nextToken());
				d = Integer.parseInt(st.nextToken());
				adj[u].add(new Node(v, c, d));
			}
			
			dijkstra(1);
			res = INF;
			for (int i = 0; i <= m; i++) {
				if (visit[n][i] && res > dist[n][i])
					res = dist[n][i];
			}
			
			System.out.println(res == INF ? "Poor KCM" : res);
		}
	}
	
	static void dijkstra(int s) {
		
		PriorityQueue<Node> q = new PriorityQueue<>(50000, new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				return o1.v - o2.v;
			}
		});
		
		Node cur;
		int money;
		int distance;
		
		dist[s][0] = 0; // 1의 도시로 0의 돈으로 가는 최소경로
		q.offer(new Node(s, 0, 0));
		
		while (!q.isEmpty()) {
			cur = q.poll();
			
			if (cur.d > dist[cur.v][cur.m]) continue;
			
			for (Node next : adj[cur.v]) {
				money = next.m + cur.m;
				distance = next.d + cur.d;
				if (money > m) continue;
				if (!visit[next.v][money] || distance < dist[next.v][money]) {
					visit[next.v][money] = true;
					dist[next.v][money] = distance;
					q.offer(new Node(next.v, money, distance));
				}
			}
		}
	}
}

djm03178 5년 전 0

73번째 줄이 잘못됐습니다. 거기만 고치니 통과되네요.

irnd04 5년 전 0

선생님 저번에 이어 고맙습니다.

변수이름의 중요성을 한번더 깨닫고갑니다.!

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

문제

문제

출처

ICPC

제 실력으론 시간초과가 넘기기가 힘드네요 도와주세요

irnd04 5년 전 0

djm03178 5년 전 0

irnd04 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

​제 실력으론 시간초과가 넘기기가 힘드네요 도와주세요

irnd04 5년 전 0

djm03178 5년 전 0

irnd04 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

제 실력으론 시간초과가 넘기기가 힘드네요 도와주세요