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 (voucher) ofD 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.
Title summary: PAT consists of a series of subject tests. Each test is divided into several levels. To qualify for Level B, Level A must be passed with a score of no less than S, and Level A becomes a prerequisite for Level B. Meanwhile, those who pass Level A with a score of no less than S will receive a voucher to take Level B. Currently, this PAT is only in the design stage, so people can make different plans. If there exists some test T such that T is its own precondition, then the plan is inconsistent. Your task is to test each plan and judge whether it is consistent and at the same time find out the easiest way to obtain a test certificate in any subject (with a minimum total score of S). If the easiest way isn’t unique, figure out a way to get the largest total amount of vouchers.
Analysis: The node structure is used to store the node information in the shortest path. It overloads the operation rule of the less than sign (<) so that the priority queue can be arranged in the order required by the question. Bian is a structure used to store side information. E is an adjacency list that stores side information. Dis stores the distance of the shortest path, the minimum score to be tested from the source point to the i-th point, and the maximum number of vouchers that can be obtained. f is used to mark whether there is a loop. When it is 1, it means there is a loop. Corresponding to the description in the question, a certain course is its own prerequisite course. Both in and in2 are used to store the in-degree of each node, and the Last array stores the previous node of each node in the shortest path.
First, we can use the method of constructing topological sorting to determine whether there is a cycle in the graph. You can use bfs to store the node with the current in-degree of 0 in the queue. After taking it out, reduce the in-degree of all reachable nodes by 1. Finally, see how many nodes can be reached with an in-degree of 0. Each time Store them in S, and finally look at the relationship between the size of S and N. If they can all be obtained, it means there is no loop.
First establish an initial point, here 1002 is used as the initial point, and then connect the node with an in-degree of 0 to this initial point. In this way, just use 1002 as the starting point, and then use Dijkstra to calculate the shortest path and the corresponding node of each node.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
int v, score, voucher;
bool operator < (const node & amp;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) & amp; & amp; (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.\
";
else cout << "Impossible.\
";
for (int i = 1, q; i <= T; i + + ) {
cin >> q;
if(!in[q]) cout << "You may take test " << q << " directly.\
";
else if(!f) cout << "Error.\
";
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 << '\
';
}
}
return 0;
}