单源最短路径算法分析，洛谷_P3371 【模板】单源最短路径（弱化版）_dijkstra_堆优化

洛谷_P3371 【模板】单源最短路径（弱化版）_dijkstra_堆优化

// dijkstra最短路算法_堆优化 
#include<bits/stdc++.h>
using namespace std;
#define ERROR ( (1LL<<31)-1 )   // 1LL ( (int)1 溢出 ) const int INF=0x3f3f3f3f;
const int N=2e6+7;
int h[N],pos;      
struct edge{ int y,data,next; }e[N]; 
int n,m,start;  
// h[i]: 存放结点i的第一个邻接点在边表e[i]中的下标
// pos: 边表下标推进器
// e[]: 边表 int dis[N];                 // start到其他所有点的最短路径
bool used[N];               // 标记顶点是否被当成中间点使用过 used[i]=1:表示顶点i被使用过void init()                 // 初始化函数
{pos=0;memset( h,-1,sizeof( h ) );memset( dis,0x3f,sizeof( dis ) );memset( used,0,sizeof( used ) );
}// e[++pos]=edge( y,data,h[x] ); 这句话没法实现存边
void add( int x,int y,int data )	// 存边
{e[pos].y=y;e[pos].data=data;e[pos].next=h[x];h[x]=pos++;
}struct node
{int id,dis;				// 结构体的构造函数 用于结构体的初始化node( int a,int b ):id(a),dis(b) {}bool operator < ( const node& x ) const {return x.dis<dis;   // (2)<(1) 表示从小到大排列 放入优先队列当中相当于小堆顶}                       // 注意和 sort 区分开来, (1)<(2) 才表示从小到大排列 
};void dijkstra()
{dis[start]=0;priority_queue<node> q;int x,y,data,i;q.push( node( start,0 ) );while( !q.empty() ){x=q.top().id; q.pop();    		// 获取优先队列(小堆顶)的堆顶元素 获取的顶点是距离起点start最近的点if( used[x] ) continue; 		// 使用过就返回used[x]=1;              		// 标记 下面将使用x作为中间顶点更新最短路径dis[]for( i=h[x];~i;i=e[i].next ){y=e[i].y;                   // 获取顶点 x 的邻接点data=e[i].data;             // 获取边(x,y) 的权值if( dis[y]>dis[x]+data )    // 如果可以更新 记得加入小堆顶{dis[y]=dis[x]+data;q.push( node( y,dis[y] ) );}}}
}int main()
{int x,y,data,i;while( cin>>n>>m>>start ){init();                 // 初始化while( m-- ){cin>>x>>y>>data;add( x,y,data );    // 有向图// add( y,x,data ); 无向图请加上这句代码}dijkstra();for( i=1;i<=n;i++ ){if( i!=1 ) cout<<" ";if( dis[i]==INF )   cout<<ERROR;else                cout<<dis[i];}cout<<endl;}return 0;
}

单源最短路径算法分析，