pb_ds
pb_ds库包括：
优先队列
平衡二叉树
Hash
准则：
需要合并时用pairing_heap_tag
使用时需要的库：
#include
#include
#include
#include
using namespace __gnu_pbds; 定义变量：
typedef __gnu_pbds::priority_queue heap; //默认从大到小
typedef __gnu_pbds::priority_queue > heap; //默认从小到大heap q;
heap::point_iterator id;//-----------------------------------------------------typedef tree,rb_tree_tag,tree_order_statistics_node_update> rbtree;
rbtree q,qq;//-----------------------------------------------------gp_hash_tableh; 使用方法：
//优先队列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<pb_ds+Dijktra
#include
#include
#include
#include
#include
typedef long long ll;
#define pa pair
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue > 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]);
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！