7-4 Professional Ability Test (30 分)
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 Dwhere 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->...->THowever, 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 7Sample 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->7Sample 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 1Sample Output 2:
Impossible.
You may take test 3 directly.
Error.题目限度：
题目粗心：
有 N 个考试，M 个考试的相互之间的关系，当初咱们把这 N 场考试和 M 条关系称之为一个考试打算，请问以后的打算是否是一个 consistent 的打算，并给出了 K 场考试的查问，如果是一个 consistent 的打算，要求给出通过以后考试最为疾速的办法，如果有多种，抉择取得代金券最多的那种。如果不是一个 consistent 的打算，那么判断以后考试 T 是否能够间接考取，如果是就输入 You may take test T directly. 否则输入Error.。
算法思路：
首先得了解题意，plan 是指每一个测试用例，而不是每一个查问，consistent 的判断办法就是判断以后图中是否有环，因为是有向图，能够应用拓扑排序来进行判断.
对于含有环的图，须要晓得以后查问的结点是否入度为 0，因而应用 zeroDegree 汇合保留每一个入度为 0 的结点 (inDegree 在拓扑排序的时候会发生变化)，对于入度为 0 的点间接输入You may take test T directly. 就好，否则输入 Error.
对于不含有环的图，咱们须要找到一条到查问结点的最短门路，这里应用迪杰斯特拉算法解决，然而没有给定终点，认真读题发现终点肯定是那些读入为 0 的结点，因为只有入度为 0 的点能力没有任何前置条件进行考试，然而如果对每一个入度为 0 的终点进行遍历取得最短门路的话，最初两个测试点会运行超时，所以这里采纳一个小技巧，咱们认为设立一个顶点，其入度为 0，并且将该顶点指向以后图中的所有入度为 0 的顶点，并且边权设置为 0，这样整个图中入度为 0 的顶点就恰好只有一个了，每一个顶点的最短门路的获取只须要执行一遍迪杰斯特拉算法即可。
这里简要阐明下为什么该办法可行，因为从该点登程，肯定先经原图中入度为 0 的终点，也就是真正的终点，那么该图中所有结点的最短门路肯定是比拟了所有原图中终点之后所取得的，并且边权为 0，不会影响最短距离。
而后对于每一个查问的考生科目，判断是否在原图中是入度为 0 的结点，如果是，输入You may take test T directly.，否则应用 DFS 遍历该结点的门路(在获取最短距离的时候，每一个结点的前驱保留在了 pre 数组中，因而能够间接获取)
留神点：
- 1、如果屡次应用迪杰斯特拉算法，最初两个测试点会超时。
提交后果：
AC 代码：
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<unordered_set>
using namespace std;
int N,M;// 顶点数和边数
vector<int> Adj[1005];// 邻接表
int score[1005][1005];//score[a][b]代表 a 测试点取得的最低得分能够有资格考 b 考试
int voucher[1005][1005];//voucher[a][b]代表 a 测试点取得 score[a][b]及以上分数能够失去考 b 的代金券
int inDegree[1005];// 每一个顶点的入度
bool inQueue[1005];// 标记曾经入队的节点
unordered_set<int> zeroDegree;// 图中所有入度为 0 的顶点, 这里指原图中入度为 0 的顶点
// 拓扑排序判断是否有环存在
bool topologicalOrder(){
queue<int> q;
int num = 0;
// 入队所有入度为 0 的顶点
for(int i=0;i<N;++i){if(inDegree[i]==0){inQueue[i] = true;
q.push(i);
}
}
while (!q.empty()){int t = q.front();
q.pop();
++num;// 统计入队的结点个数
// 将 t 的临界点的入度全副减一
for(int vertex:Adj[t]){--inDegree[vertex];
// 将入度为 0 且没有入队的节点入队
if(inDegree[vertex]==0){q.push(vertex);
}
}
}
return num==N;// true 示意没有环
}
int dis[1005];// 每一个节点到终点的最短距离(分数)
int money[1005];// 每一个节点到终点取得到最大代金券
bool visited[1005];// 标记每一个节点是否拜访
int pre[1005];// 每一个节点的前驱节点
void Dijsktra(int start){fill(dis,dis+1005,0x3ffffff);
dis[start] = 0;
money[start] = 0;
for(int i=0;i<N+1;++i){// N+ 1 个顶点
// 找出间隔终点最短的未拜访节点
int min_dis = 0x3fffff;
int min_index = -1;
for(int j=0;j<N+1;++j){if(!visited[j]&&dis[j]<min_dis){min_dis = dis[j];
min_index = j;
}
}
if(min_index==-1) return;
visited[min_index] = true;
// 优化门路
for(int j=0;j<Adj[min_index].size();++j){int v = Adj[min_index][j];
if(!visited[v]){if(dis[v]>dis[min_index]+score[min_index][v]){
// 以后门路更短
pre[v] = min_index;
dis[v] = dis[min_index]+score[min_index][v];
money[v] = money[min_index] + voucher[min_index][v];
} else if(dis[v]==dis[min_index]+score[min_index][v]&&money[v]<money[min_index]+voucher[min_index][v]){
// 须要考试的分数一样，然而取得的代金券更多
pre[v] = min_index;
money[v] = money[min_index] + voucher[min_index][v];
}
}
}
}
}
void DFS(int end){if(pre[end]==N){
// 达到终点
printf("%d",end);
return;
}
DFS(pre[end]);
printf("->%d",end);
}
void consistent(int query[],int K){Dijsktra(N);// 取得每一个结点的最短距离和门路
for(int i=0;i<K;++i){if(zeroDegree.find(query[i])!=zeroDegree.end()){
// 以后考试没有前置条件
printf("You may take test %d directly.",query[i]);
}else{DFS(query[i]);
}
if(i<K-1) printf("\n");
}
}
void notConsistent(int query[],int K){for(int i=0;i<K;++i){if(zeroDegree.find(query[i])!=zeroDegree.end()){
// 以后考试没有前置条件
printf("You may take test %d directly.",query[i]);
}else{printf("Error.");
}
if(i<K-1) printf("\n");
}
}
int main(){scanf("%d %d",&N,&M);
for (int i = 0; i < M; ++i) {
int a,b;
scanf("%d %d",&a,&b);
scanf("%d %d",&score[a][b],&voucher[a][b]);
++inDegree[b];
Adj[a].push_back(b);
}
// 增加一个入度为 0 的顶点, 顶点编号为 N, 与所有入度为 0 的顶点连贯一条边，这样 N 就是惟一的入度为 0 的顶点了
for(int i=0;i<N;++i){if(inDegree[i]==0){Adj[N].push_back(i);
zeroDegree.insert(i);
}
}
int K;
scanf("%d",&K);
int query[K];
for(int i=0;i<K;++i){scanf("%d",&query[i]);
}
bool isOk = topologicalOrder();
if(isOk){printf("Okay.\n");
consistent(query,K);
} else {printf("Impossible.\n");
notConsistent(query,K);
}
return 0;
}