백준 소스코드 [C++] 13907 세금

www.acmicpc.net/problem/13907

13907번: 세금

백준 소스코드 [C++] 13907 세금

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v), v.end())
typedef long long ll;
using namespace std;

#define MAX 987654321
int V, E, K, v, e, weight;
vector <pii>adj[1001];
int res[1001][1001];
int src,sink;

struct Node{
    int idx,depth,cost;
    Node(int idx,int depth,int cost){
        this->idx=idx;
        this->depth=depth;
        this->cost=cost;
    }
    bool operator<(const Node& N) const{
        return this->cost > N.cost;
    }
};

void dijkstra(){
    
    for(int i=1;i<=V;i++){
        for(int j=0;j<=1000;j++)
         res[i][j]=MAX;
    }
    
    priority_queue<Node> pq;
    pq.push(Node(src,0,0));
    res[src][0]=0;
    
    while(!pq.empty()){
        int here = pq.top().idx;
        int depth = pq.top().depth;
        int cost = pq.top().cost;
        pq.pop();
        
        if (depth==V || res[here][depth++]<cost) continue;
        
        for(auto ith: adj[here]){
            int nextcost = cost + ith.second;
            int there = ith.first;
            
            if(res[there][depth]>nextcost){
                res[there][depth]=nextcost;
                pq.push(Node(there,depth,nextcost));
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> V >> E >> K;
    cin>>src>>sink;
    
    for (int i = 0;i < E;i++) {
        cin >> v >> e >> weight;
        adj[v].push_back({ e,weight });
        adj[e].push_back({ v,weight });
    }
    
    dijkstra();
    
    vector<pii> dest;
    for(int depth=0;depth<=1000;depth++)
    if(res[sink][depth]!=MAX) dest.push_back({depth,res[sink][depth]});
    
    int tax=0,temp;
    for(int i=0;i<=K;i++){
      
        int val=INT_MAX;
        for(auto a: dest) val=min(val,a.first*tax+a.second);
        cout<<val<<'\n';
        
        if(i==K) break;
        cin>>temp;
        tax+=temp;
    }
    return 0;
}