红色餐饮网站源码/搜索引擎seo是什么意思

Description

N个点，M条边的有向图，求点1到点N的最短路（保证存在）。
1<=N<=1000000，1<=M<=10000000

Input

第一行两个整数N、M，表示点数和边数。
第二行六个整数T、rxa、rxc、rya、ryc、rp。

前T条边采用如下方式生成：
1.初始化x=y=z=0。
2.重复以下过程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的有向边。

后M-T条边采用读入方式：
接下来M-T行每行三个整数x,y,z，表示一条从x到y长度为z的有向边。

1<=x,y<=N，0<z,rxa,rxc,rya,ryc,rp<2^31

 

Output

一个整数，表示1~N的最短路。

Sample Input

3 3
0 1 2 3 5 7
1 2 1
1 3 3
2 3 1

Sample Output

2

HINT

 

【注释】

请采用高效的堆来优化Dijkstra算法。

 

 

纯粹迪杰……

orz kpm 2S：

#include<cstdio>
#include<algorithm>
using namespace std;struct na{int y,ne;long long z;na(){ne=0;}
};
struct dui{long long v;int n;
};
const long long INF=1e17;
int n,c,m,l[1000001],r[1000001],x,y,z,pp,num=0,p[1000001],nu;
na b[10000001];
dui d[1000001];
char cc;
long long read(){long long a=0;cc=getchar();while(cc<'0'||cc>'9') cc=getchar();while(cc>='0'&&cc<='9') a=a*10+cc-48,cc=getchar();return a;
}
void in(int x,int y,int z){num++;if (l[x]==0) l[x]=num;else b[r[x]].ne=num;b[num].y=y;b[num].z=z;r[x]=num;
}
void sw(int a,int b){swap(p[d[a].n],p[d[b].n]);swap(d[a],d[b]);
}
void utz(int x){while(x>1&&d[x].v<d[x>>1].v) sw(x,x>>1),x>>=1;
}
void dtz(int j){j=j*2;while(j<=nu){if (j<nu&&d[j].v>d[j+1].v) j++;sw(j>>1,j);j*=2;}sw(j>>1,nu);p[d[nu].n]=0;nu--;
}
int main(){long long rxa,rxc,rya,ryc,rp,t;n=read();m=read();t=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read();nu=n;x=y=z=0;for (int i=1;i<=t;i++){long long a,b;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);in(a,b,1e8-100*a);}for (int i=1;i<=m-t;i++){x=read();y=read();z=read();in(x,y,z);}for (int i=1;i<=n;i++) d[i].v=INF,d[i].n=i,p[i]=i;d[1].v=0;for (int i=1;i<=n;i++){x=d[1].n;long long y=d[1].v;if (x==n) {printf("%lld\n",y);return 0;}dtz(1);for (int j=l[x];j;j=b[j].ne)if (p[b[j].y]&&d[p[b[j].y]].v>y+b[j].z){d[p[b[j].y]].v=y+b[j].z;utz(p[b[j].y]);}}
}