admin 管理员组文章数量: 1184232
pb
pb_ds库包括：
优先队列
平衡二叉树
Hash
准则：
需要合并时用pairing_heap_tag
使用时需要的库：
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;定义变量：
typedef __gnu_pbds::priority_queue<int> heap; //默认从大到小
typedef __gnu_pbds::priority_queue<int,greater<int> > heap; //默认从小到大heap q;
heap::point_iterator id;//-----------------------------------------------------typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
rbtree q,qq;//-----------------------------------------------------gp_hash_table<int,bool>h;使用方法：
//优先队列while (!q.empty()) q.pop();for (int i=1;i<=10;i++)q.push(i);auto it=q.push(11);q.modify(it,50);cout<<q.top()<<endl;q.erase(it);cout<<q.top()<<endl;assert ( q. top () == 10);for (int i=10;i<=20;i++)qq.push(i);
q.join(qq);
cout<<q.top();//---------------------------------------
//树for (int i=1;i<=20;i+=2) q.insert(i);
// 插入序列 1、3、5、7、9、11、13、15、17、19cout<<q.order_of_key(5)<<endl;
// 小于5的个数auto x=q.find_by_order(6);
rbtree::iterator it=q.find_by_order(6);
// 查找第6大的数，0 为起点cout<<*x<<endl;
cout<<*it<<endl;
// 输出结果为 13q.erase(it);
x=q.find_by_order(6);
cout<<*x<<endl;
q.insert(13);
// 输出结果为 15auto z=q.lower_bound(16);
cout<<*z<<endl;
//大于等于16的第一个数auto zz=q.upper_bound(17);
cout<<*zz<<endl;
//大于16的第一个数for (int i=21;i<=40;i+=2) qq.insert(i);
q.join(qq);
for (auto x:q) cout<<x<<' ';cout<<endl;
// 输出结果为 1、3、5......37、39
//注意合并的两颗树的值域的范围不能相交q.split(29,qq);
for (auto x:q) cout<<x<<' ';cout<<endl;
//小于等于29的元素在q，其余在qq//---------------------------------------
//Hashh[1]=1;
cout<<h[1]<<endl;for (auto x:h) cout<<x.second<<endl;pb_ds+Dijktra
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
typedef long long ll;
#define pa pair<ll,int>
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<pa,greater<pa> > heap;
const int N=1e6+5,M=1e7+5;
const ll INF=1e15;
inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int n,m,T,rxa,rxc,rya,ryc,rp,a,b;
int x,y,z;
struct edge{int v,w,ne;
}e[M];
int cnt,h[N];
inline void ins(int u,int v,int w){cnt++;e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}ll d[N];
heap q;
heap::point_iterator id[N];
void dij(){for(int i=1;i<=n;i++) d[i]=INF;d[1]=0;id[1]=q.push(mp(0,1));while(!q.empty()){int u=q.top().second;q.pop(); //printf("u %d\n",u);for(int i=h[u];i;i=e[i].ne){int v=e[i].v,w=e[i].w;if(d[v]>d[u]+w){d[v]=d[u]+w;if(id[v]!=0) q.modify(id[v],mp(d[v],v));else id[v]=q.push(mp(d[v],v));}}}
}
int main(){//freopen("in.txt","r",stdin);n=read();m=read();T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read();m=m-T;while(T--){x=y=z=0;x=((ll)x*rxa+rxc)%rp;y=((ll)y*rya+ryc)%rp;a=min(x%n+1,y%n+1);b=max(y%n+1,y%n+1);ins(a,b,100000000-100*a);}while(m--) x=read(),y=read(),z=read(),ins(x,y,z);dij();printf("%lld",d[n]);
}
本文标签： pb
版权声明：本文标题：pb 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700377408a420625.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论