[백준/JAVA] 13907번 세금

https://www.acmicpc.net/problem/13907

13907번: 세금

 

 

문제분석

세금이 오를 때 마다 간선의 비용이 증가한다.

각각 오를 때 마다의 출발점에서 도착점까지의 최소비용을 출력하라.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n,m,k,s,d;
    static int[][] mindist;
    static List<Pair>[] adjList;

    static void init() throws IOException{
        n=rstn(); m=rstn(); k=rstn(); s=rstn(); d=rstn();
        adjList = new ArrayList[n+1];
        mindist = new int[n+1][n+1];
        for(int i=0; i<=n; ++i) Arrays.fill(mindist[i], 0x3f3f3f3f);
        for(int i=1; i<=n; ++i) adjList[i] = new ArrayList<>();
        for(int i=0; i<m; ++i){
            int v1=rstn(),v2=rstn(),w=rstn();
            adjList[v1].add(new Pair(v2,w));
            adjList[v2].add(new Pair(v1,w));
        }
    }

    static void dijk(){
        PriorityQueue<Triple> pq = new PriorityQueue<>(Comparator.comparingInt(o->o.y));
        pq.add(new Triple(s,0,0));
        mindist[s][0] = 0;

        while(!pq.isEmpty()){
            Triple cur = pq.poll();
            if(mindist[cur.x][cur.z] < cur.y) continue;
            if(cur.z == n) continue;
            for(Pair nxt : adjList[cur.x]){
                int nd = cur.y+nxt.y;
                if(mindist[nxt.x][cur.z+1] > nd){
                    pq.add(new Triple(nxt.x,nd,cur.z+1));
                    mindist[nxt.x][cur.z+1] = nd;
                }
            }
        }
    
    }
    

    
    public static void main (String[] args) throws IOException{
        init();
        dijk();
        //초기 최소비용
        bw.append(Integer.toString(Arrays.stream(mindist[d]).min().getAsInt())).append("\n");
        while(k-->0){
            int up = rn();
            int min = Integer.MAX_VALUE;
            for(int i=1; i<=n; ++i){
                mindist[d][i] += i*up;
                min = Math.min(min,mindist[d][i]);
            }
            bw.append(Integer.toString(min)).append("\n");
        }
        bw.flush();
    }
    
    
    ///////////////////////////////////////////////////////////

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int rn() throws IOException {return Integer.parseInt(br.readLine());}
	static void est() throws IOException {st = new StringTokenizer(br.readLine());}
	static int rstn() throws IOException {if(st==null||!st.hasMoreTokens()) est(); return Integer.parseInt(st.nextToken());}
	static int[] ra() throws IOException {return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();}
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,-1,0,1};
	static boolean chk(int x, int y, int n, int m){return x<0 || y<0 || x>=n || y>=m;}
	static class Pair{int x; int y;public Pair(int x, int y) {this.x = x;this.y = y;}}
	static class Triple{ int x,y,z;public Triple(int x, int y,int z) {this.x = x;this.y = y;this.z = z;}}
	static class Quad{ int w,x,y,z;public Quad(int w, int x, int y,int z) {this.w = w; this.x = x;this.y = y;this.z = z;}}
    static void inputinit()throws IOException{System.setIn(new FileInputStream("input.txt"));br = new BufferedReader(new InputStreamReader(System.in));}
}

 

풀이

v=1,000  e=30,000 k=30,000 

세금이 오를 때 마다 다익스트라를 돌린다고 가정하면 k * e * log v == 9,000,000,000 시간안에 풀 수 없는 문제이다.

따라서 dist 배열을 정점으로만 관리하는 것이 아닌 dist[정점][거쳐온 횟수] 로 설정하여 생성하였다. 

그 이유는 세금이 2만큼 올랐다고 가정했을 때 

s에서 d까지 한번에 왔으면 2만큼 비용이 증가할것이고 

s - v1 - d와같이 간선 두개를 거쳤다면 2,2가 증가하여 4가 증가할 것이다. 

따라서 정점,거쳐온 횟수로 구한뒤에 한번 세금이 오를 때 마다 거쳐온 횟수만큼의 세금을 곱해서 더하고 그 배열에 대해서 최솟값을 구한다면 

1번의 다익스트라 + v크기만큼의 배열 k번 갱신 으로 시간제한 안에 들어오게 된다.