algospot - nthlon

//algospot - nthlon
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define INF 1000000
 
int M;
vector<vector<pair<int, int>>> adj;
 
void init()
{
    cin >> M;
    adj = vector<vector<pair<int, int>>>(400);
    int x, y, gap;
    for(int i = 0; i<M; i++)
    {
        cin >> x >> y;
        gap = x-y;
        for(int j = 1; j<400; ++j)
        {
            if(j+gap < 1 || j+gap >= 400) continue;
 
            adj[j].push_back(make_pair(j+gap, x));
        }
        adj[0].push_back(make_pair(200+gap, x));
    }
}
 
void dijkstra()
{
    vector<int> bucket(400, INF);
    priority_queue<pair<int, int>> pq;
    bucket[0] = 0;
    pq.push(make_pair(0, 0));
 
    int here, cost;
    while(!pq.empty())
    {
        here = pq.top().second;
        cost = -pq.top().first;
        pq.pop();
 
        if(cost > bucket[here]) continue;
 
        for(int i = 0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i].first;
            int c = adj[here][i].second;
            if(c+cost < bucket[there])
            {
                bucket[there] = c+cost;
                pq.push(make_pair(-(c+cost), there));
            }
        }
    }
    if(bucket[200] == INF)
        cout << "IMPOSSIBLE" << "\n";
    else
        cout << bucket[200] << "\n";
}
 
int main()
{
    int C; cin >> C;
    for(int t_num = 0; t_num < C; ++t_num)
    {
        init();
        dijkstra();
    }
}

 

 

 

 

 

https://algospot.com/judge/problem/read/NTHLON

algospot.com :: NTHLON

 

 

 

 

 

nthlon

그래프로 모델링을 해서 해결합니다.

종목을 완주하는데 걸리는 시간이 1~200 를 벗어나지 않기 떄문에

두 선수 사이의 시간의 차는 -199~199 를 벗어나지 않습니다.

두 선수 사이의 시간의 차를 정점으로 하고, 종목을 간선으로 하는 그래프를 만들수 있습니다.

간선의 가중치는 두 선수중 아무나 선택해 해당 종목에서 걸리는 시간으로 합니다.

시작 정점을 위한 가상의 정점을 만들고, 모든 종목에 대해 발생할 수 있는 시간 차, 즉 정점과

연결시킵니다.

위의 그래프에서 가상의 정점과 시간의 차가 0을 나타내는 정점까지의 최단거리가 문제에서의 답입니다!