题解:
模板题,地界特斯拉+堆优化
注意第一种建边
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+,M=1e7+;
ll dis[N];
int a1,b1,c3,a,b,c,a2,b2,a3,b3,T,n,m,num,l;
int fi[N],zz[M],sl[M],ne[M],f[N],q[N],p;
void jb(int x,int y,int z)
{
ne[++num]=fi[x];
fi[x]=num;
zz[num]=y;
sl[num]=z;
}
void up(int x)
{
if (x==)return;
if (dis[f[x]]<dis[f[x/]])
{
swap(f[x],f[x/]);
swap(q[f[x]],q[f[x/]]);
up(x/);
}
}
void down(int x)
{
int i=x;
if (x*<=l&&dis[f[i]]>dis[f[x*]])i=x*;
if (x*<l&&dis[f[i]]>dis[f[x*+]])i=x*+;
if (i!=x)
{
swap(f[x],f[i]);
swap(q[f[x]],q[f[i]]);
down(i);
}
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d%d%d%d%d%d",&T,&a1,&a2,&b1,&b2,&p);
m-=T;
while (T--)
{
a=(ll)((ll)a*a1+a2)%p;
b=(ll)((ll)b*b1+b2)%p;
a3=min(a%n+,b%n+);
b3=max(a%n+,b%n+);
c3=1e8-a3;
jb(a3,b3,c3);
}
while (m--)
{
scanf("%d%d%d",&a3,&b3,&c3);
jb(a3,b3,c3);
}
memset(dis,0x3f3f3f3f,sizeof dis);
dis[]=;
for (int i=;i<=n;i++)f[i]=q[i]=i;
l=n;
for (int i=;i<=n;i++)
{
int k=f[];
if (k==n)break;
q[f[l]]=;
f[]=f[l--];
down();
for (int j=fi[k];j;j=ne[j])
if (dis[zz[j]]>dis[k]+sl[j])
{
dis[zz[j]]=dis[k]+sl[j];
up(q[zz[j]]);
}
}
printf("%lld",dis[n]);
}