[그래프][시도x] NTHLON 철인 N종 경기

1. 문제

 

A나라와 B나라가 경기를 한다고 한다.

 

이때 종목들과 종목마다 두 나라 선수의 예상 기록이 주어질때

 

두 나라를 무승부로 만들려고한다.

 

이때 가장 짧은 기록을 구하는 문제이다.

 

만약 무승부가 될 수 없으면 IMPOSSIBLE을 출력한다.

 

 

2. 책의 풀이: 그래프의 생성

 

만들수 있는 코스는 무한히 많다.

 

따라서 완전 탐색으로 이 문제를 풀기 불가능하지만 

 

모든 코스를 다 만들어 봐야하는 것은 아니다.

 

힌트는 종목들 간의 순서가 상관이 없다는 것이다.

 

 

이 문제에서 종목들의 종류나 순서는 중요하지 않다.

 

의미 있는 것은 두 선수의 예상 시간 차이 뿐이다.

 

코스에 종목을 하나 추가하면, 그 종목에 따라 차이는 변화한다.

 

이와 같은 정보를 그래프로 표현하려면

 

A국 선수의 예상 시간에서 B국 선수의 예상 시간을 뺀값을 정점으로 표현하는 것이다.

 

그러면 각 종목은 그래프의 간선이 되고, 코스는 그래프 위의 경로가 된다.

 

 

 

종착점을 0 또다른 0을 시작점으로 설정하고

 

각 간선에 적절한 가중치, 한 선수가 걸리는 예상 시간으로 두면

(무승부가 목표이기 때문에 한 선수로의 시간으로만으로도 문제가 풀린다.)

 

최단 경로를 구할 수 있다.

 

 

 

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
 
using namespace std;
 
const int INF = 987654321;
const int START = 401;
 
vector<pair<int, int> > adj[410];
int V;
int M;
 
vector<int> dijkstra(int start)
{
    priority_queue<pair<int, int> > pq;
    vector<int> ret = vector<int>(V, INF);
    ret[start] = 0;
    pq.push(make_pair(0, start));
    while(!pq.empty())
    {
        int here = pq.top().second, cost = -pq.top().first; pq.pop();
 
        if(ret[here] < cost) continue;
 
        for(int i = 0; i < adj[here].size(); i++)
        {
            int there = adj[here][i].first;
            int nextDist = adj[here][i].second + cost;
            if(ret[there] > nextDist)
            {
                pq.push(make_pair(-nextDist, there));
                ret[there] = nextDist;
            }
        }
    }
    return ret;
}
 
int vertex(int delta)
{
    return delta + 200;
}
int solve(const vector<int>& a, const vector<int>& b)
{
    V = 402;
    for(int i = 0; i < V; i++) adj[i].clear();
    for(int i = 0; i < a.size(); i++) {
        int delta = a[i] - b[i];
        adj[START].push_back(make_pair(vertex(delta), a[i]));
    }
    for(int delta = -200; delta <= 200; delta++)
    {
        for(int i = 0; i < a.size(); i++)
        {
            int next = delta + a[i] - b[i];
            if(abs(next) > 200) continue;
            adj[vertex(delta)].push_back(make_pair(vertex(next), a[i]));
        }
    }
    vector<int> shortest = dijkstra(START);
    int ret = shortest[vertex(0)];
    if(ret == INF) return -1;
    return ret;
}
int main()
{
    int C;
    cin>>C;
    while(C--)
    {
        cin>>M;
        vector<int> a(M), b(M);
        for(int i = 0; i < M; i++ )
        {
            int a1, b1;
            cin>>a1>>b1;
            a[i] = a1;
            b[i] = b1;
        }
        int ret = solve(a, b);
        if(ret == -1)
            cout<<"IMPOSSIBLE\n";
        else
            cout<<ret<<"\n";
    }
}

NTHLON