网页设计公司网站制作,人力资源公司简介模板,wordpress婚恋网模板,娱乐类网站开发目录 大根堆
小根堆
set#xff08;小根堆#xff09; 大根堆
题目链接#xff1a;洛谷 P3243 菜肴制作
题目描述
知名美食家小 A 被邀请至 ATM 大酒店#xff0c;为其品评菜肴。ATM 酒店为小 A 准备了 n 道菜肴#xff0c;酒店按照为菜肴预估的质量从高到低给予 1 到…目录 大根堆
小根堆
set小根堆 大根堆
题目链接洛谷 P3243 菜肴制作
题目描述
知名美食家小 A 被邀请至 ATM 大酒店为其品评菜肴。ATM 酒店为小 A 准备了 n 道菜肴酒店按照为菜肴预估的质量从高到低给予 1 到 n 的顺序编号预估质量最高的菜肴编号为 1。
由于菜肴之间口味搭配的问题某些菜肴必须在另一些菜肴之前制作具体的一共有 m 条形如 i 号菜肴必须先于 j 号菜肴制作的限制我们将这样的限制简写为 (i,j)。
现在酒店希望能求出一个最优的菜肴的制作顺序使得小 A 能尽量先吃到质量高的菜肴
也就是说 在满足所有限制的前提下1 号菜肴尽量优先制作。 在满足所有限制1 号菜肴尽量优先制作的前提下2 号菜肴尽量优先制作。 在满足所有限制1 号和 22 号菜肴尽量优先的前提下3 号菜肴尽量优先制作。 在满足所有限制1 号和 2 号和 3 号菜肴尽量优先的前提下4 号菜肴尽量优先制作。 以此类推。
例 1共 4 道菜肴两条限制 (3,1)、(4,1)那么制作顺序是 3,4,1,2。
例 2共 5 道菜肴两条限制 (5,2)、(4,3)那么制作顺序是 1,5,2,4,3。
例 1 里首先考虑 1因为有限制 (3,1) 和 (4,1)所以只有制作完 3 和 4 后才能制作 1而根据 33 号又应尽量比 4 号优先所以当前可确定前三道菜的制作顺序是 3,4,1接下来考虑 2确定最终的制作顺序是 3,4,1,2。
例 2 里首先制作 1 是不违背限制的接下来考虑 2 时有 (5,2) 的限制所以接下来先制作 55 再制作 2接下来考虑 3 时有 (4,3) 的限制所以接下来先制作 4 再制作 3从而最终的顺序是 1,5,2,4,3。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!首字母大写其余字母小写
输入格式
第一行是一个正整数 t表示数据组数。接下来是 t 组数据。对于每组数据第一行两个用空格分开的正整数 n 和 m分别表示菜肴数目和制作顺序限制的条目数。接下来 m 行每行两个正整数 x,y表示 x 号菜肴必须先于 y 号菜肴制作的限制。
输出格式
输出文件仅包含 t 行每行 n 个整数表示最优的菜肴制作顺序或者 Impossible! 表示无解。
输入输出样例
输入 #1复制
3
5 4
5 4
5 3
4 2
3 2
3 3
1 2
2 3
3 1
5 2
5 2
4 3
输出 #1复制
1 5 3 4 2
Impossible!
1 5 2 4 3
说明/提示
【样例解释】
第二组数据同时要求菜肴 1 先于菜肴 2 制作菜肴 2 先于菜肴 3 制作菜肴 3 先于。
菜肴 1 制作而这是无论如何也不可能满足的从而导致无解。
【数据范围】
100% 的数据满足 n,m≤1051≤t≤3。
m 条限制中可能存在完全相同的限制。 思想用大根堆不用小根堆的原因用小根堆只能找到小点但是无法保证能先选到1在前面的点比如4 25 1那么小根堆会优先选择4 2这样的排列顺序不符合题意要想1出现在前面那么可以反向建边用大根堆这样的排列顺序就是5 1最后再翻转输出就可以了。 代码
// Problem: D - 菜肴制作
// Contest: Virtual Judge - 2023暑期训练-图论part1
// URL: https://vjudge.net/contest/574296#problem/D
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;typedef long long ll;const int N 2e55;int n,m;
int in[N];
vectorint edge[N];
vectorint ans;void toposort(){priority_queueint q;//q.clear();for(int i1;in;i){if(in[i]0){q.push(i);}}while(!q.empty()){int tq.top();q.pop();ans.push_back(t);for(int i0;iedge[t].size();i){in[edge[t][i]]--;if(in[edge[t][i]]0){q.push(edge[t][i]);}}}if(ans.size()n){coutImpossible!\n;}else{for(int in-1;i0;i--){coutans[i] ;}cout\n;}}int main(){int T;cinT;while(T--){cinnm;ans.clear();memset(in,0,N);for(int i0;iN;i){edge[i].clear();}for(int i1;im;i){int x,y;cinxy;edge[y].push_back(x);in[x];}toposort();}return 0; }题目链接代码源 最短路
给你一张 n 个顶点 m 条边的有向简单图顶点编号从 1 到 n每条边都有一个边权边权为非负整数。
现在有 k 组询问每组询问读入两个整数 x,y请求出从 x 号点到 y 号点的最短路的长度。如果不存在从 x 号点到 y 号点的路径请输出 -1。
输入格式
第一行三个整数 n,m,k表示图的顶点数、边数和询问次数。
接下来 m 行每行三个整数 x,y,z表示 x 号点到 y 号点有一条边权为 z 的有向边。
接下来 k 行每行两个整数 x,y表示一组询问。
输出格式
输出共 k 行每行一个数表示一组询问的答案。
样例输入
3 3 2
1 2 3
2 3 2
3 2 1
1 3
3 1
样例输出
5
-1
数据规模
对于所有数据保证 2≤n≤5000,0≤m≤10000,1≤k≤5,1≤x,y≤n,1≤z≤10000。 思想set是一种数据结构可以维护数据按照从小到大的顺序排列 小根堆
priority_queuepii,vectorpii,greaterpii q;
#includebits/stdc.h
using namespace std;typedef long long ll;
typedef pairint,int pii;const int N 2e55;struct node{int y,v; //连接的边以及边权node(int _y,int _v){y_y;v_v;}
};vectornode edge[N1];
int dist[N1];
int n,m,k;
priority_queuepii,vectorpii,greaterpii q;
bool st[N];void dijkstra(int s,int t){memset(dist,127,N1);memset(st,false,N);dist[s]0;//q.clear();for(int i1;in;i){q.push({dist[i],i});}while(!q.empty()){int xq.top().second;q.pop();if(st[x]) continue;st[x]true;for(auto i:edge[x]){if(dist[x]i.vdist[i.y]){dist[i.y]dist[x]i.v;q.push({dist[i.y],i.y});}}}if(dist[t]130){coutdist[t]\n;}else{cout-1\n;}}int main(){cinnmk;for(int i1;im;i){int x,y,z;cinxyz;edge[x].push_back(node(y,z));}for(int i1;ik;i){int s,t;cinst;dijkstra(s,t);}return 0; } set小根堆
#includebits/stdc.h
using namespace std;typedef long long ll;
typedef pairint,int pii;const int N 2e55;struct node{int y,v; //连接的边以及边权node(int _y,int _v){y_y;v_v;}
};vectornode edge[N1];
int dist[N1];
int n,m,k;
setpii se;void dijkstra(int s,int t){memset(dist,127,N1);dist[s]0;se.clear();for(int i1;in;i){se.insert({dist[i],i});}while(!se.empty()){int xse.begin()-second;if(xt||dist[x]130){break;}se.erase(se.begin());for(auto i:edge[x]){if(dist[x]i.vdist[i.y]){se.erase({dist[i.y],i.y});dist[i.y]dist[x]i.v;se.insert({dist[i.y],i.y});}}}if(dist[t]130){coutdist[t]\n;}else{cout-1\n;}}int main(){cinnmk;for(int i1;im;i){int x,y,z;cinxyz;edge[x].push_back(node(y,z));}for(int i1;ik;i){int s,t;cinst;dijkstra(s,t);}return 0; }
