题目大意：最短路。
思路：最短路。
贴一份比较高效的堆优化Dij模板吧。
CODE：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define _MAX 1000010
#define MAX 10000010
using namespace std;
#define min(a,b) ((a) < (b) ? a:b)
long long f[_MAX];
struct Heap{
int num[_MAX],pos[_MAX],size;
void PushUp(int p) {
while(p > 1) {
if(f[num[p]] < f[num[p >> 1]]) {
swap(num[p],num[p >> 1]);
swap(pos[num[p]],pos[num[p >> 1]]);
p >>= 1;
}
elsebreak;
}
}
void Insert(long long x) {
num[++size] = x;
pos[x] = size;
PushUp(size);
}
void Pop() {
pos[num[1]] = 0;
num[1] = num[size--];
if(size)pos[num[1]] = 1;
int now = 2;
while(now < size) {
if(f[num[now + 1]] < f[num[now]])
++now;
if(f[num[now]] < f[num[now >> 1]]) {
swap(num[now],num[now >> 1]);
swap(pos[num[now]],pos[num[now >> 1]]);
now <<= 1;
}
elsebreak;
}
}
}heap;
int points,edges;
long long T,rxa,rxc,rya,ryc,rp;
int head[_MAX],total;
int next[MAX],aim[MAX],length[MAX];
inline void Add(int x,int y,int len)
{
next[++total] = head[x];
aim[total] = y;
length[total] = len;
head[x] = total;
}
void Dijkstra()
{
memset(f,0x3f,sizeof(f));
f[1] = 0;
for(int i = 1; i <= points; ++i)
heap.Insert(i);
while(heap.size) {
int x = heap.num[1]; heap.Pop();
for(int i = head[x]; i; i = next[i])
if(f[aim[i]] > f[x] + length[i])
f[aim[i]] = f[x] + length[i],heap.PushUp(heap.pos[aim[i]]);
}
}
int main()
{
cin >> points >> edges;
cin >> T >> rxa >> rxc >> rya >> ryc >> rp;
int x = 0,y = 0,z = 0;
int a,b;
for(int i = 1; i <= T; ++i) {
x = ((long long)x * rxa + rxc) % rp;
y = ((long long)y * rxa + rxc) % rp;
a = min(x % points + 1,y % points + 1);
b = y % points + 1;
if(a != b)Add(a,b,1e8 - 100 * a);
}
for(int i = T + 1; i <= edges; ++i) {
scanf("%d%d%d",&x,&y,&z);
Add(x,y,z);
}
Dijkstra();
cout << f[points] << endl;
return 0;
}