算法问题实战策略 NTHLON

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

 #include <iostream>

 #include <vector>

 #include <algorithm>

 #include <queue>

 using namespace std;

 int V;

 //图的邻接表表示法 保存成对(连接的顶点序号 边线加权值)

 vector<pair<int, int>> adj[];

 const int START = ;

 const int INF = 0x3f3f3f3f;

 vector<int> dijkstra(int src)

 {

     vector<int > dist(V, INF);

     dist[src] = ;

     priority_queue<pair<int, int>> pq;

     pq.push(make_pair(, src));

     while (!pq.empty()) {

         int cost = -pq.top().first;

         int here = pq.top().second;

         pq.pop();

         if (dist[here] < cost) continue;

         for (int i = ; i < adj[here].size(); ++i) {

             int there = adj[here][i].first;

             int nextDist = cost + adj[here][i].second;

             if (dist[there] > nextDist) {

                 dist[there] = nextDist;

                 pq.push(make_pair(-nextDist, there));

             }

         }

     }

     return dist;

 }

 //==========================================================

 //返回(A国选手的预想耗时-B国家选手的预想耗时)的顶点序号

 int vertex(int delta) {

     return delta + ;

 }

 //a[]=A国选手的各项预想耗时

 //b[]=B国选手的各项预想耗时

 int solve(const vector<int>& a, const vector<int>& b) {

     //生成图结构

     V = ;

     for (int i = ; i < V; i++) adj[i].clear();

     for (int i = ; i < a.size(); i++) {

         int delta = a[i] - b[i];

         adj[START].push_back(make_pair(vertex(delta), a[i]));

     }

     //当前耗时之差

     for (int delta = -; delta <= ; ++delta) {

         //若添加第i个比赛项目

         for (int i = ; i < a.size(); ++i) {

             int next = delta + a[i] - b[i];

             //没有必要生成耗时之差超过200的顶点

             if (abs(next) > ) continue;

             adj[vertex(delta)].push_back(make_pair(vertex(next), a[i]));

         }

     }

     vector<int> shortest = dijkstra(START);

     int ret = shortest[vertex()];

     if (ret == INF) return -;

     return ret;

 }

 int main()

 {

     int n,m;

     cin >> n;

     while (n--) {

         cin >> m;

         vector<int> va;

         vector<int> vb;

         for (int i = ; i < m; i++) {

             int a, b;

             cin >> a >> b;

             va.push_back(a);

             vb.push_back(b);

         }

         int ret = solve(va, vb);

         if (ret != -) {

             cout << ret << endl;

         }

         else {

             cout << "IMPOSSIBLE" << endl;

         }

     }

     return ;

 }