Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a prerequisite (前置要求) of Level B if one must pass Level A with a score no less than S in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than S will receive a voucher（代金券）of D yuans (Chinese dollar) for taking Level B.
At the moment, this PAT is only in design and hence people would make up different plans. A plan is NOT consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total S) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (≤1000) and M, being the total numbers of tests and prerequisite relations, respectively. Then M lines follow, each describes a prerequisite relation in the following format:
T1 T2 S D
where T1 and T2 are the indices (from 0 to N−1) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.
Then another positive integer K (≤N) is given, followed by K queries of tests. All the numbers in a line are separated by spaces.
Output Specification:
Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.
If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:
T0->T1->…->T
However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.
If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.
Sample Input 1:
8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7
Sample Output 1:
Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7
Sample Input 2:
4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1
Sample Output 2:
Impossible.
You may take test 3 directly.
Error.
题目大意：PAT由一系列学科测试组成。每个测试被划分为几个级别。如果要资格参加 Level B，那么必须以不低于 S 的分数通过 Level A，Level A 就成为 Level B 的前置要求。同时，以不低于 S 的分数通过 Level A 的人将获得一张代金券，用于参加 Level B。目前，这个PAT仅处于设计阶段，因此人们可以制定不同的计划。如果存在某个测试 T，使得 T 是其自身的前提条件，那么该计划就不一致。您的任务是测试每个计划，并判断它是否一致，并同时找出获得任何学科测试证书的最简单方法（具有最小总分S）。如果最简单的方法不唯一，找出一个可以获得最大代金券总额的方法。
分析：node结构用来存储最短路中的结点信息，其中重载了小于号(<)的运算规则，让优先队列能以题目要求的顺序排列。bian是用来存储边信息的结构体。E是存储边信息的邻接表，Dis中存储最短路的距离，存的是从源点到第i个点所要考的最少分数和可以获得的最多的代金券。f用来标记是否有环，为1时表示有环，对应题目中说明的，某个课程是自己的前置课程。in和in2都用来存储每个结点的入度，Last数组存储最短路中每个结点的前一个结点是什么。
首先，我们可以用构造拓扑排序的方法判断一下图中是否存在环。可以使用bfs，将当前入度为0的结点存在队列里，取出后将其所有能到达的结点的入度减1，最后看一下能让入度为0的结点有多少，每次把他们存在S中，最后看S的大小和N之间的关系，如果全部都能拿到，则说明无环。
先建立一个初始点，这里用1002当初始点，然后把入度为0的结点和这个初始点连接上。这样只要使用1002当作起点，然后用Dijkstra计算最短的路径，和对应的每个结点上一步的结点是什么。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> #include <vector> #include <queue> using namespace std; struct node { int v, score, voucher; bool operator < (const node &x) const { if(score != x.score) return score > x.score; else return voucher < x.voucher; } }; struct bian { int next, S, D; }; vector<bian> E[1005]; vector<pair<int,int>> Dis(1005, {2e9, -1}); int N, M, T1, T2, S, D, f, T, in[1005], in2[1005], Last[1005]; queue<int> DAG; int huan() { vector<int> S; while(DAG.size()) { int now = DAG.front(); DAG.pop(); S.push_back(now); for(auto it : E[now]) { in2[it.next]--; if(!in2[it.next]) DAG.push(it.next); } } return S.size() == N; } void dijkstra() { vector<int> vis(1005); priority_queue<node> Q; Q.push({1002, 0, 0}); Dis[1002].first = Dis[1002].second = 0; while(Q.size()) { node now = Q.top(); Q.pop(); if(vis[now.v]) continue; vis[now.v] = 1; Dis[now.v].first = now.score; Dis[now.v].second = now.voucher; for (auto it : E[now.v]) { if(vis[it.next]) continue; if((Dis[it.next].first > Dis[now.v].first + it.S) || ((Dis[it.next].first == Dis[now.v].first + it.S) && (Dis[it.next].second < Dis[now.v].second + it.D))) { Dis[it.next].first = Dis[now.v].first + it.S; Dis[it.next].second = Dis[now.v].second + it.D; Last[it.next] = now.v; Q.push({it.next, Dis[it.next].first, Dis[it.next].second}); } } } return; } int main() { cin >> N >> M; for (int i = 0; i < M; i++) { cin >> T1 >> T2 >> S >> D; E[T1].push_back({T2, S, D}); in[T2]++, in2[T2]++; } for (int i = 0; i < N; i++) { if (in[i] == 0) { E[1002].push_back({i, 0, 0}); DAG.push(i); } } f = huan(); dijkstra(); cin >> T; if(f) cout << "Okay.\n"; else cout << "Impossible.\n"; for (int i = 1, q; i <= T; i++) { cin >> q; if(!in[q]) cout << "You may take test " << q << " directly.\n"; else if(!f) cout << "Error.\n"; else { vector<int> path; int now = q; while(q != 1002) { path.push_back(q); q = Last[q]; } for (int j = path.size() - 1; j >= 0; j--) { cout << path[j]; if(j) cout << "->"; } cout << '\n'; } } return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
