[백준 13907번 C/C++] 세금

 

[백준 13907번 C/C++] 세금

 

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

13907번: 세금

---

 

 

해결전략

 

다익스트라 알고리즘 Dijistra Algorithm

최단경로

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 987654321;

int n, m, k; // n: 도시의 수, m: 도로의 수, k: 세금 인상 횟수
int s, d;
vector<vector<pair<int, int>>> road;

struct Path {
	int city, cost;

	Path(int a, int b) {
		city = a;
		cost = b;
	}

	bool operator<(const Path& oper) const {
		return cost < oper.cost;
	}
};

int Calc(int tax)
{
	vector<int> dist(n + 1, INF);

	priority_queue<Path> pQ;
	pQ.push({ s, 0 }); // 시작도시 s, 비용 0 을 시작값으로 설정
	dist[s] = 0;

	int answer = INF;
	while (!pQ.empty())
	{
		int nowCity = pQ.top().city;
		int nowCost = pQ.top().cost;
		pQ.pop();
		//cout << nowCity << ", " << nowCost << "\n";

		if (nowCity == d) { // 도착도시 d에 도달한 경우
			answer = min(answer, nowCost);
		}

		if (dist[nowCity] < nowCost) continue;

		for (int i = 0; i < road[nowCity].size(); i++)
		{
			int nextCity = road[nowCity][i].first;
			int nextCost = nowCost + road[nowCity][i].second + tax;

			if (dist[nextCity] > nextCost) {
				dist[nextCity] = nextCost;
				pQ.push({ nextCity, nextCost });
			}
		}
	}

	return answer;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m >> k;
	cin >> s >> d;
	road.resize(n + 1);

	int a, b, w;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> w; // 양뱡향 도로
		road[a].push_back({ b, w });
		road[b].push_back({ a, w }); 
	}

	int tax = 0;
	cout << Calc(tax) << "\n";
	for (int i = 0; i < k; i++) {
		int tmp;
		cin >> tmp;
		tax += tmp;
		cout << Calc(tax) << "\n";
	}

	return 0;
}

 

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 987654321;

int n, m, k; // n: 도시의 수, m: 도로의 수, k: 세금 인상 횟수
int s, d;    // s: 시작 도시, d: 목적지 도시
vector<vector<pair<int, int>>> road; // 각 도시별 연결된 도로와 비용을 저장하는 벡터
vector<vector<int>> dist;            // 최소 비용을 저장하는 벡터

struct Path {
    int city, cost, cnt; // 현재 도시, 현재까지의 비용, 경로에 포함된 도시의 수

    Path(int a, int b, int c) { // 생성자
        city = a;
        cost = b;
        cnt = c;
    }

    // 우선순위 큐에서 비용이 낮은 것을 높은 우선순위로 처리하기 위해 비교 연산자 수정
    bool operator>(const Path& oper) const {
        return cost > oper.cost;
    }
};

void Calc() // 최소 비용 계산 함수
{
    priority_queue<Path, vector<Path>, greater<Path>> pQ; // 비용이 낮은 것이 높은 우선순위로 오도록 수정
    pQ.push({ s, 0, 0 }); // 시작도시 s, 비용 0 을 시작값으로 설정
    dist[s][0] = 0;

    while (!pQ.empty())
    {
        int nowCity = pQ.top().city; // 현재 도시
        int nowCost = pQ.top().cost; // 현재까지의 비용
        int nowCnt = pQ.top().cnt;   // 경로에 포함된 도시의 수
        pQ.pop();

        if (dist[nowCity][nowCnt] < nowCost) continue; // 이미 더 적은 비용으로 방문한 경우, 무시


        for (int i = 0; i < road[nowCity].size(); i++)
        {
            int nextCity = road[nowCity][i].first; // 다음 도시
            int nextCost = nowCost + road[nowCity][i].second; // 다음 도시까지의 총 비용
            int nextCnt = nowCnt + 1; // 경로에 포함된 도시의 수 증가

            if (nextCnt < n && dist[nextCity][nextCnt] > nextCost) { // 다음 도시의 최소 비용 갱신 조건 확인. 추가된 경로의 개수가 n 미만일 때만 갱신
                dist[nextCity][nextCnt] = nextCost;       // 최소 비용 갱신
                pQ.push({ nextCity, nextCost, nextCnt }); // 우선순위 큐에 삽입
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    cin >> s >> d;
    road.resize(n + 1);
    dist.resize(n + 1, vector<int>(n + 1, INF));

    int a, b, w;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> w; // 양방향 도로
        road[a].push_back({ b, w });
        road[b].push_back({ a, w });
    }

    Calc();

    int answer = INF;
    for (int i = 0; i < n; i++) { // 모든 가능한 경로를 확인하여 최소 비용 계산       
        answer = min(answer, dist[d][i]);
    }
    cout << answer << "\n";

    int tax = 0; // 세금 초기값
    for (int i = 0; i < k; i++)
    {
        int input;
        cin >> input; // 세금 인상 입력 받기
        tax += input; // 세금 인상

        int answer = INF;
        for (int j = 0; j < n; j++) // 세금 인상 후 비용 계산
        {
            answer = min(answer, dist[d][j] + j * tax);
		}

		cout << answer << "\n";
	}

	return 0;
}

 

---