题意
给定一个 (N) 个点，(M) 条有向边的带非负权图，请你计算从 (S) 出发，到每个点的距离。
数据保证你能从 (S) 出发到任意点。
(1≤N≤100000)；
(1≤M≤200000)；
分析
可以将Dijkstra算法的运行时间改善到(O(V lg V+E))，方法是使用斐波那契堆。
每次ExtractMin操作的摊还代价为(O(lg V))，每次DecreaseKey操作的摊还代价为(O(1))。
但是渐进性能更优不代表实际运行更优，尤其是现在的电脑水平。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<ctime>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
rg T data=0;
rg int w=1;
rg char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return data*w;
}
template<class T>T read(T&x)
{
return x=read<T>();
}
typedef long long ll;
co ll INF=0x7fffffffffffffff;
co int N=1e5+7;
int root;
namespace FIB
{
using std::vector;
using std::swap;
co double PHI=(sqrt(5)+1)/2; // log_{PHI}(N)=ln(N)/ln(PHI)
// Heap node definitions
int sz;
int fa[N],ch[N];
int left[N],right[N];
int degree[N];
bool mark[N];
ll val[N];
// Heap node operations
int newnode(int nd,ll v)
{
fa[nd]=0,ch[nd]=0;
left[nd]=right[nd]=nd;
degree[nd]=0;
mark[nd]=false;
val[nd]=v;
return nd;
}
void add(int r,int x)
{
assert(r&&x);
left[right[r]]=x,right[x]=right[r];
right[r]=x,left[x]=r;
}
void del(int r)
{
left[right[r]]=left[r];
right[left[r]]=right[r];
left[r]=right[r]=r; // edit 2
}
// Heap definitions
int nm;
int min[2],siz[2];
// Heap operations
int NewHeap()
{
++nm;
min[nm]=0;
siz[nm]=0;
return 0;
}
void Insert(int H,int x)
{
if(!min[H])
min[H]=x;
else
{
add(min[H],x);
if(val[x]<val[min[H]])
min[H]=x;
}
++siz[H];
}
int Minimum(int H)
{
return min[H];
}
int Union(int H1,int H2)
{
if(!min[H1])
return H2;
if(!min[H2])
return H1;
int t=min[H2];
while(min[H2])
{
int x=min[H2];
if(x==right[x])
min[H2]=0;
else
min[H2]=right[x];
del(x);
add(min[H1],x);
}
if(val[t]<val[min[H1]])
min[H1]=t;
siz[H1]+=siz[H2];
return H1;
}
void Link(int y,int x)
{
del(y);
if(!ch[x])
ch[x]=y;
else
add(ch[x],y);
fa[y]=x;
++degree[x];
mark[y]=false;
}
void Consolidate(int H)
{
co int D=log(siz[H])/log(PHI)+1;
vector<int>A(D);
fill(A.begin(),A.end(),0);
while(min[H]) // edit 1
{
int x=min[H];
if(right[x]==x)
min[H]=0;
else
min[H]=right[x];
del(x);
int d=degree[x];
while(A[d])
{
int y=A[d];
if(val[x]>val[y])
swap(x,y);
Link(y,x);
A[d]=0;
++d;
}
assert(d<D);
A[d]=x;
}
min[H]=0;
for(int i=0;i<D;++i)
if(A[i])
{
if(!min[H])
min[H]=A[i];
else
{
add(min[H],A[i]);
if(val[A[i]]<val[min[H]])
min[H]=A[i];
}
}
}
int ExtractMin(int H)
{
int z=min[H];
if(z)
{
while(ch[z])
{
int x=ch[z];
if(right[x]==x)
ch[z]=0;
else
ch[z]=right[x];
del(x);
add(z,x);
fa[x]=0;
}
if(z==right[z])
min[H]=0;
else
{
min[H]=right[z];
del(z);
Consolidate(H);
}
--siz[H];
}
return z;
}
void Cut(int H,int x,int y)
{
if(x==right[x]) // edit 3
ch[y]=0;
else
{
ch[y]=right[x];
del(x);
}
--degree[y];
add(min[H],x);
fa[x]=0;
mark[x]=false;
}
void CascadingCut(int H,int y)
{
int z=fa[y];
if(z)
{
if(mark[y]==false)
mark[y]=true;
else
{
Cut(H,y,z);
CascadingCut(H,z);
}
}
}
void DecreaseKey(int H,int x,ll v)
{
assert(v<=val[x]);
val[x]=v;
int y=fa[x];
if(y&&val[x]<val[y])
{
Cut(H,x,y);
CascadingCut(H,y);
}
if(val[x]<val[min[H]])
min[H]=x;
}
void Delete(int H,int x)
{
DecreaseKey(H,x,-INF);
ExtractMin(H);
}
}
using namespace FIB;
using namespace std;
int n,m,s;
vector<pair<int,ll> >g[N];
ll dis[N];
bool inh[N];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m),read(s);
for(int i=1;i<=m;++i)
{
int x=read<int>(),y=read<int>();
ll w=read<ll>();
g[x].push_back(make_pair(y,w));
}
root=NewHeap();
fill(dis+1,dis+n+1,INF);
dis[s]=0;
Insert(root,newnode(s,0));
inh[s]=1;
while(siz[root])
{
int x=Minimum(root);
ExtractMin(root);
inh[x]=0;
for(int i=0;i<g[x].size();++i)
{
int y=g[x][i].first,w=g[x][i].second;
if(dis[x]+w<dis[y])
{
dis[y]=dis[x]+w;
if(!inh[y])
{
Insert(root,newnode(y,dis[y]));
inh[y]=1;
}
else
DecreaseKey(root,y,dis[y]);
}
}
}
for(int i=1;i<=n;++i)
printf("%lld ",dis[i]);
return 0;
}
题意
N个点，M条边的有向图，求点1到点N的最短路（保证存在）。
(1 leq N leq 1000000，1 leq M leq 10000000)
前T条边采用如下方式生成：
- 初始化x=y=z=0。
- 重复以下过程T次：
x=(x*rxa+rxc)%rp;
y=(y*rya+ryc)%rp;
a=min(x%n+1,y%n+1);
b=max(y%n+1,y%n+1);
则有一条从a到b的，长度为1e8-100*a的有向边。
分析
B君：想一下出题人怎么造数据卡你。首先把所有边反向，然后及时跳出。那T条边是随机的，我猜它没用，我试着一点一点删掉，最后发现就算不加那T条边还是能AC。
大概是说面向数据编程。得知了这种逆天做法以后，果断试着用hzwer的配对堆水过去。
配对堆……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
#define ll long long
#define pa pair<ll,int>
#define llinf 9000000000000000000LL
using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<pa,greater<pa>,pairing_heap_tag > heap;
int n,m,cnt,last[1000005];
int T,rxa,rxc,rya,ryc,rp;
heap::point_iterator id[1000005];
int x,y,z;
ll dis[1000005];
struct data{int to,next,v;}e[10000005];
inline 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;
}
void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
}
void dijkstra()
{
heap q;
for(int i=1;i<=n;i++)dis[i]=llinf;
dis[1]=0;id[1]=q.push(make_pair(0,1));
while(!q.empty())
{
int now=q.top().second;q.pop();
for(int i=last[now];i;i=e[i].next)
if(e[i].v+dis[now]<dis[e[i].to])
{
dis[e[i].to]=e[i].v+dis[now];
if(id[e[i].to]!=0)
q.modify(id[e[i].to],make_pair(dis[e[i].to],e[i].to));
else id[e[i].to]=q.push(make_pair(dis[e[i].to],e[i].to));
}
}
}
int main()
{
n=read();m=read();
T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read();
int a,b;
for(int i=1;i<=m-T;i++)
{
x=read(),y=read(),z=read();
insert(x,y,z);
}
dijkstra();
printf("%lld",dis[n]);
return 0;
}