[CODEGROUND] 할인권

다익스트라 알고리즘을 활용하는 문제이다.

source부터 destination까지의 최단 거리를 구한 후 세일하는 티켓의 가격과 비교해서 작은 지 큰지를 비교한다.

만약 source부터 destination까지 바로 가는 구간이 있다면 바로 티켓과 비교하면 된다.

다익스트라를 처음 구현해본다면 시간이 걸릴 문제이지만 

간단하게 구할 수 있는 문제이다.

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <functional> using namespace std; #define PAIR pair < int,int > #define INT_MAX 2147483647 int sale_ticket, ticket_count, station_count; vector < vector < int > > station; priority_queue < PAIR > plan; priority_queue < PAIR, vector < PAIR > , greater < PAIR > > cache; //거리, station vector < int > min_price, visited; void min_way(int start) { cache.push(make_pair(0, start)); while (!cache.empty()) { int distance = cache.top().first; int station_index = cache.top().second; cache.pop(); visited[station_index] = 1; for (int index = 1; index <= station_count; index++) { if (station[station_index][index] != -1 && visited[index] == 0) { if (min_price[index] > distance + station[station_index][index]) { min_price[index] = distance + station[station_index][index]; cache.push(make_pair(min_price[index], index)); } } } } } void travel() { int before_start = -1; while (!plan.empty()) { int start = plan.top().first; int end = plan.top().second; plan.pop(); if (station[start][end] != -1) { if (station[start][end] > sale_ticket) ticket_count++; } else { if (before_start != start) { while (!cache.empty()) cache.pop(); min_price = vector < int > (station_count + 1, INT_MAX); visited = vector < int > (station_count + 1, 0); min_way(start); before_start = start; } if (min_price[end] > sale_ticket) ticket_count++; } } } int main() { int for_count, road_count, start, end, price, plan_count; cin >> for_count; for(int i=1;i<=for_count;i++) { station.clear(); cin >> station_count >> road_count >> sale_ticket; station = vector < vector < int > > (station_count + 1, vector < int > (station_count + 1, -1)); while (road_count--) { cin >> start >> end >> price; station[start][end] = price; station[end][start] = price; } cin >> plan_count; while (plan_count--) { cin >> start >> end; plan.push(make_pair(start, end)); } ticket_count = 0; travel(); cout << "Case #" << i << endl; cout << ticket_count << endl; } }