AcWing 5074. 机场登机口调整模拟
原题链接
中等
作者:
ober02
,
2024-03-27 09:06:52
,
所有人可见
,
阅读 6
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
struct pn{
int pri, port;
bool operator<(const pn& p)const{
if(p.pri != this->pri){
return this->pri < p.pri;
}
else{
return this->port > p.port;
}
}
};
int n;
const int N = 500;
int h[N], ne[N], e[N], idx;
int portnum; //登机口数量
void add(int a, int b){ // a --> b
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
memset(h ,-1, sizeof h);
cin >> n;
while(n--){
int a, b[3];
cin >> a;
for(int i = 0; i < 3 ;i++) cin >> b[i]; // 反着插入,为了bfs 顺序
for(int i = 2; i >= 0 ; i--) {
if(b[i] != -1){
add(a, b[i]);
if(b[i] < 100) portnum++;
}
}
}
pn pri_node[110];
for(int i = 0; i< portnum ; i++){
int pri, port;
cin >> port >> pri;
pri_node[i] = {pri, port};
}
sort(pri_node, pri_node + portnum);
//BFS
queue<int> q;
q.push(100);//插入根节点
while(q.size())
{
int a = q.front();
q.pop();
if(a < 100){ // 登机口
cout << pri_node[--portnum].port << " " << a << endl;
}
for(int i = h[a]; i != -1; i = ne[i])
{
int j = e[i];
q.push(j);
}
}
}