问题思考：
- 首先，若所有的计划(plan)中的节点都可达，则输出 Okay
，否则输出 Impossible。注意：这里的“plan”判断的是整个图（这里是有向图）上的节点，而不只是那K个queries节点。若存在环，则必然在经历一趟拓扑排序之后，还有留存节点未能遍历到，即判断环内有节点不可达。 - 其次，每个query对应输出最佳plan，要求S（score ）最少的基础上多争取D（voucher）。这里的麻烦在于，如何化成一个单源最短路问题（这里显然可能存在多个
节点是没有前置要求的，即“You may take test i directly”的，即“多源”的最短路）？—— 一个技巧性的做法就是，额外设置一个起点（与所有
- 并用一个Last数组在每选出一条最短路边的时候记录上个节点，用来到时候追溯回去，一直追溯到预设的起点。因为该起点和所有的
- 若先输出Okay，则之后根据Last数组输出each query节点的最短路
- 若先输出Impossible，之后只需判断query是否直接可达无需前置要求，否则输出Error。
代码实现：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m, k, in[1005], in2[1005], f, last[1005];
struct node {
int v, score, voucher;
bool operator < (const node &x) const {
if (score != x.score) return score > x.score;
return voucher < x.voucher;
}
};
struct edge {
int next, s, d;
};
vector<edge> E[1005]; // 邻接表的简洁表示
queue<int> que;
vector<pair<int, int>> dis(1002, {2e9, -1});
bool circle() {
vector<int> S;
while (que.size()) {
int now = que.front();
que.pop();
S.push_back(now);
for (auto x : E[now]) {
in2[x.next]--;
if (!in2[x.next]) que.push(x.next);
}
}
return S.size() == n;
}
void dijkstra() {
vector<int> vis(1005);
priority_queue<node> Q;
Q.push({1002, 0, 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 x : E[now.v]) {
if (vis[x.next]) continue;
if (dis[x.next].first > dis[now.v].first + x.s ||
((dis[x.next].first == dis[now.v].first + x.s)
&& (dis[x.next].second < dis[now.v].second + x.d))) {
dis[x.next].first = dis[now.v].first + x.s;
dis[x.next].second = dis[now.v].second + x.d;
last[x.next] = now.v;
Q.push({x.next, dis[x.next].first, dis[x.next].second});
}
}
}
return ;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, s, d;
scanf("%d%d%d%d", &a, &b, &s, &d);
// 构建邻接表
E[a].push_back(edge{b, s, d});
in[b]++, in2[b]++;
}
// 寻找无前置要求的节点
for (int i = 0; i < n; i++) {
if (in[i] == 0) {
E[1002].push_back({i, 0, 0}); // 起点与无前置要求的节点相连
que.push(i);
}
}
f = circle();
dijkstra();
cin >> k;
if (f) cout << "Okay.\n";
else cout << "Impossible.\n";
for (int i = 0, q; i < k; i++) {
scanf("%d", &q);
if (!in[q]) cout << "You may take test " << q << " directly.\n";
else if (!f) cout << "Error.\n";
else {
vector<int> path;
while (q != 1002) {
path.push_back(q);
q = last[q];
}
for (int j = path.size() - 1; j >= 0; j--) {
cout << path[j];
j && cout << "->";
}
cout << '\n';
}
}
return 0;
}知识点：小于号重载
- 这里需要注意，重载小于号的方向，下面是一个实验样例。
#include<iostream>
#include<vector>
#include<queue>
struct node {
int v, score, voucher;
bool operator < (const node &x) const {
if (score != x.score) return score > x.score;
return voucher < x.voucher;
}
};
int main() {
priority_queue<node> que;
que.push(node{0, 1, 2});
que.push(node{1, 1, 3});
que.push(node{2, 2, 2});
while (que.size()) {
node now = que.top(); que.pop();
cout << "now : " << now.v << " " << now.score << " " << now.voucher << endl;
}
return 0;
}- 运行结果：
now : 1 1 3
now : 0 1 2
now : 2 2 2可见如果想要让自定义结构满足按其某个property从小到大排序，就得这么写：
bool operator < (const node &x) const {
return this.property > x.property
}
