P4779【模板】单源最短路径（标准版）题解bifanwen的博客-

原题链接

简要题意：

给定一个有向图，求从源点开始到各点的最短路。

前置知识：

P3371 【模板】单源最短路径（弱化版）

首先，我们考虑把原来
$text{Dijkstra}$

Dijkstra 的算法考虑优化。

对于每个节点，松弛相邻节点，这部分无法优化。

但是寻找
$text{dis}$

dis 最小值的过程，我们可以用 优先队列（即小根堆）实现。

怎么实现呢？

考虑一开始源点入队，队列记录每个点的 当前
$text{dis}$

dis 最小值 和编号。

对当前节点，把所有相邻的节点松弛一遍，并把松弛成功的节点入队。

但是你发现一个问题，如果一个点被它相邻的点同时更新多次，就会入队多次，然后把一模一样的松弛进行很多遍，然后
$O(n^2)$

O(n2) 没了。

所以 因为我们开的是优先队列，因此入队的节点距离小的在前，每次对于相同的一个节点，先遍历的一定最优。因此可以开一个哈希记录是否走过，走过则不走即可。

时间复杂度：
$O(n log n)$

O(nlogn).

实际得分：
$O(100pts)$

O(100pts).

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int N=2e5+1; inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();} int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; int n,m,s,dis[N]; bool vis[N]; vector<pair<int,int> > G[N]; inline void Dijkstra(int s) {  dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()) { int x=q.top().second;   q.pop(); if(vis[x]) continue; vis[x]=1; //判断哈希 //  printf("%dn",x); for(int i=0;i<G[x].size();i++) { int v=G[x][i].first,w=G[x][i].second; if(dis[v]>dis[x]+w) {     dis[v]=dis[x]+w; if(!vis[v]) q.push(make_pair(dis[v],v)); //松弛入队 } } } } int main(){  n=read(),m=read(),s=read(); memset(dis,0x3f,sizeof(dis)); while(m--) { int u=read(),v=read(),w=read();   G[u].push_back(make_pair(v,w)); } Dijkstra(s); for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts(""); return 0; }