有人说BZOJ3040用普通的<queue>中priority_queue搞dijkstra过不了。
我只想说你们的djk可能写的太丑了。
先上代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<ext/pb_ds/priority_queue.hpp> #define pir pair<ll,int> using namespace std; typedef long long ll; //typedef std::priority_queue<pir,vector<pir>,greater<pir> > heap; //3840 ms typedef __gnu_pbds::priority_queue<pir,greater<pir> > heap;//默认是pairing_heap_tag //3304 ms 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 node{ int v,w,next; }e[M]; int cnt,head[N];ll dis[N];bool vis[N]; inline void add(int u,int v,int w){ e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt; } heap q; inline void dijkstra(){ int S; for(int i=1;i<=n;i++) dis[i]=INF; dis[S=1]=0; q.push(make_pair(dis[S],S)); while(!q.empty()){ pir t=q.top();q.pop(); int x=t.second; if(vis[x]) continue; vis[x]=1; for(int i=head[x];i;i=e[i].next){ int v=e[i].v; if(!vis[v]&&dis[v]>dis[x]+e[i].w){ dis[v]=dis[x]+e[i].w; q.push(make_pair(dis[v],v)); } } } } int main(){ n=read();m=read(); T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read(); m=m-T; x=rxc%rp;y=ryc%rp; a=min(x%n+1,y%n+1); b=max(y%n+1,y%n+1); while(T--) add(a,b,100000000-100*a); while(m--) x=read(),y=read(),z=read(),add(x,y,z); dijkstra(); printf("%lld",dis[n]); return 0; }
对比：
| English | Vietnamese |
In this problem, you have to maintain a dynamic set of numbers which support the two fundamental operations
and the two type of queries
If the parameter is a value x, it is guaranteed that 0 ≤ |x| ≤ 109. If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 109.
For each query, print the corresponding result in a single line. In particular, for the queries K-TH, if k is larger than the number of elements in S, print the word ‘invalid‘.
Input 8 I -1 I -1 I 2 C 0 K 2 D -1 K 1 K 2 Output 1 2 2 invalid
#include<cstdio> #include<ext/pb_ds/assoc_container.hpp> //pb_ds库这次内置了红黑树（red-black tree）、伸展树（splay tree）和排序向量树（ordered-vector tree，没找到通用译名，故自行翻译）。 //这些封装好的树都支持插入（insert）、删除（erase）、求kth（find_by_order）、求rank（order_of_key）操作，O(logn)内完成 using namespace std; using namespace __gnu_pbds; int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbt; //SPOJG++版本稍旧(4.3.2),需要写成null_mapped_type才可以(高级版本可以写null_type) char in(){ for(char ch=getchar();;ch=getchar()) if(ch>=‘A‘&&ch<=‘Z‘) return ch; } int main(){ char c;int x; for(int T=read();T--;){ c=in();x=read(); if(c==‘I‘){ bbt.insert(x); } else if(c==‘D‘){ bbt.erase(x); } else if(c==‘K‘){ if(x<=bbt.size()) printf("%d\n",*bbt.find_by_order(x-1)); else puts("invalid"); } else{ printf("%d\n",bbt.order_of_key(x)); } } return 0; }
原文：http://www.cnblogs.com/shenben/p/6291080.html