BZOJ 3040: 最短路(road) ( 最短路 )

淡淡的烟草味﹌ 2021-11-10 12:40 340阅读 0赞

![042247351018596.png][]

本来想学一下配对堆的...结果学着学着就偏了...

之前 kpm 写过这道题 , 前面的边不理它都能 AC .. 我也懒得去写前面的加边了...

用 C++ pb\_ds 库里的 pairing\_heap 水过去的...

\----------------------------------------------------------------------

\#include<cstdio>

\#include<cstring>

\#include<algorithm>

\#include<iostream>

\#include<ext/pb\_ds/priority\_queue.hpp>

\#define rep( i , n ) for( int i = 0 ; i < n ; ++i )

\#define clr( x , c ) memset( x , c , sizeof( x ) )

\#define Rep( i , n ) for( int i = 1 ; i <= n ; ++i )

\#define mk make\_pair

using namespace std;

using namespace \_\_gnu\_pbds;

typedef long long ll;

typedef pair< ll , int > pli;

const ll inf = ll( 1e18 );

const int maxn = 1000000 + 5;

const int maxm = 10000000 + 10;

struct edge \{

int to;

ll dist;

edge\* next;

\};

edge\* pt , E\[ maxm \];

edge\* head\[ maxn \];

void edge\_init() \{

pt = E;

clr( head , 0 );

inline void add\_edge( int u , int v , ll d ) \{

pt -> to = v;

pt -> dist = d;

pt -> next = head\[ u \];

head\[ u \] = pt++;

\_\_gnu\_pbds :: priority\_queue< pli , greater< pli > , pairing\_heap\_tag > :: point\_iterator pos\[ maxn \];

\_\_gnu\_pbds :: priority\_queue< pli , greater< pli > , pairing\_heap\_tag > Q;

ll d\[ maxn \];

int n;

void dijkstra() \{

rep( i , n ) d\[ i \] = inf;

d\[ 0 \] = 0;

Q.push( mk( 0 , 0 ) );

while( ! Q.empty() ) \{

int x = Q.top().second;

Q.pop();

for( edge\* e = head\[ x \] ; e ; e = e -> next ) \{

int to = e -> to;

if( d\[ to \] > d\[ x \] + e -> dist ) \{

d\[ to \] = d\[ x \] + e -> dist;

if( pos\[ to \] != 0 )

Q.modify( pos\[ to \] , mk( d\[ to \] , to ) );

else

pos\[ to \] = Q.push( mk( d\[ to \] , to ) );

inline int read() \{

int ans = 0;

char c = getchar();

for( ; ! isdigit( c ) ; c = getchar() );

for( ; isdigit( c ) ; c = getchar() )

ans = ans \* 10 + c - '0';

return ans;

void Read() \{

n = read();

int m = read() , t = read();

m -= t;

rep( i , 5 ) t = read();

while( m-- ) \{

int u = read() , v = read() , d = read();

u-- , v--;

add\_edge( u , v , d );

int main() \{

freopen( "test.in" , "r" , stdin );

edge\_init();

Read();

dijkstra();

cout << d\[ n - 1 \] << "\\n";

return 0;

\----------------------------------------------------------------------

## 3040: 最短路(road) ##

Time Limit: 60 Sec   Memory Limit: 200 MB  
Submit: 1843   Solved: 561  
\[ [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 ##

## HINT ##

【注释】  
  
请采用高效的堆来优化Dijkstra算法。

## Source ##

[WC2013营员交流-lydrainbowcat][WC2013_-lydrainbowcat]

转载于:https://www.cnblogs.com/JSZX11556/p/4621404.html

[042247351018596.png]: /images/20211109/4def1e849a004294b186b3036c3b394f.png
[Submit]: http://www.lydsy.com/JudgeOnline/submitpage.php?id=3040
[Status]: http://www.lydsy.com/JudgeOnline/problemstatus.php?id=3040
[Discuss]: http://www.lydsy.com/JudgeOnline/bbs.php?id=3040
[WC2013_-lydrainbowcat]: http://www.lydsy.com/JudgeOnline/problemset.php?search=WC2013%E8%90%A5%E5%91%98%E4%BA%A4%E6%B5%81-lydrainbowcat