题目

Solution

配对堆优化 d i j k s t r a dijkstra dijkstra

Code

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,int> pa;
typedef __gnu_pbds::priority_queue<pa,greater<pa>,pairing_heap_tag> heap;
#define mp make_pair
const int N=1000001;
struct node{
	int to,ne,w;
}e[10000001];
heap q;
heap::point_iterator id[N];
ll dis[N];
int n,m,T,rxa,rxc,rya,ryc,rp,a,b,x,y,z,i,tot,h[N],u;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
void add(int x,int y,int z){
	e[++tot]=(node){y,h[x],z};
	h[x]=tot;
}
int main(){
	n=read();m=read();T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read();
	for (i=0;i<T;i++){
		x=(1ll*x*rxa+rxc)%rp;
		y=(1ll*y*rya+ryc)%rp;
		b=y%n+1;
		a=min(x%n+1,b);
		add(a,b,100*(1e6-a));
	}
	for (i=0;i<m-T;i++){
		x=read();y=read();z=read();
		add(x,y,z);
	}
	memset(dis,63,(n+1)<<3);
	dis[1]=0;
	q.push(mp(0,1));
	while (!q.empty()){
		u=q.top().second;if (u==n) break;q.pop();
		for (int i=h[u],v;i;i=e[i].ne){
			v=e[i].to;
			if (dis[u]+e[i].w<dis[v]){
				dis[v]=dis[u]+e[i].w;
				if (id[v]==0) id[v]=q.push(mp(dis[v],v));
				else q.modify(id[v],mp(dis[v],v));
			}
		}
	}
	printf("%lld",dis[n]);
}

二叉堆（洛谷P4779）：

#include<bits/stdc++.h>
using namespace std;
const int N=100002;
struct node{
	int to,ne,w;
}e[N<<1];
struct kk{
	int u,d;
	bool operator <(const kk &x)const{return d>x.d;}
};
int n,m,s,i,dis[N],h[N],tot,x,y,z;
priority_queue<kk>q;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
void add(int x,int y,int z){
	e[++tot]=(node){y,h[x],z};
	h[x]=tot;
}
void dij(){
	memset(dis,63,(n+1)<<2);
	dis[s]=0;
	q.push((kk){s,0});
	while (!q.empty()){
		kk u=q.top();q.pop();
		if (u.d!=dis[u.u]) continue;//重点
		for (int i=h[u.u],v;i;i=e[i].ne){
			v=e[i].to;
			if (u.d+e[i].w<dis[v]){
				dis[v]=u.d+e[i].w;
				q.push((kk){v,dis[v]});
			}
		}
	}
}
int main(){
	n=rd();m=rd();s=rd();
	for (;m--;) x=rd(),y=rd(),z=rd(),add(x,y,z);
	dij();
	putchar('0');
	for (i=2;i<=n;i++) putchar(' '),wri(dis[i]);
}