bzoj 3040: 最短路(road)

3040: 最短路(road)

Time Limit: 60 Sec  Memory Limit: 200 MB
Submit: 3235  Solved: 1095
[Submit][Status][Discuss]

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算法。

/*
    stl的堆比手写的堆慢不了多少。
    用stl就行
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 1000010
using namespace std;
int dis[maxn],n,m,T,rxa,rxc,rya,ryc,rp,num,head[maxn];
struct node{
    int to,pre,v;
}e[maxn*10];
bool vis[maxn];
void Insert(int from,int to,int v){
    e[++num].to=to;
    e[num].v=v;
    e[num].pre=head[from];
    head[from]=num;
}
struct Node{
    int d,id;
    bool operator < (const Node b)const{
        return d>b.d;
    }
};
Node mk(int a,int b){
    Node res;
    res.d=b;res.id=a;
    return res;
}
priority_queue<Node>q;
void Dij(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;q.push(mk(1,0));
    while(!q.empty()){
        Node cur=q.top();q.pop();
        int now=cur.id;if(vis[now])continue;
        vis[now]=1;
        for(int i=head[now];i;i=e[i].pre){
            int to=e[i].to;
            if(dis[to]>dis[now]+e[i].v){
                dis[to]=dis[now]+e[i].v;
                q.push(mk(to,dis[to]));
            }
        }
    }
}
int main(){
    scanf("%d%d%d%d%d%d%d%d",&n,&m,&T,&rxa,&rxc,&rya,&ryc,&rp);
    int x,y,z,a,b;x=y=z=0;
    for(int i=1;i<=T;i++){
        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);
        Insert(a,b,1e8-100*a);
    }
    for(int i=T+1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Insert(x,y,z);
    }
    Dij();
    printf("%d",dis[n]);
}