Dijkstra 大根堆优化 单源最短路
对普通的Dijkstra，每次要找到没有标记的距离最短的点显然很麻烦，所以不如做一个单调队列，每次取堆顶就行了，由查找的n变成进堆的logn
时间复杂度有说 O(mlogn)也有一点O(mlogm)的，不过问题不大，基本是比SPFA要快的
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#define forup(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
vector<pair<int,int>>node[100005];//分别存连接的点和权值
priority_queue<pair<int,int>>q;//前一个是(-d[v])，后一个是v
int d[100005];
bool vis[100005];
int n,m,s;
void dijkstra(int s)
{
d[s]=0;
q.push({0,s});
while(!q.empty())
{
auto u=q.top().second; q.pop();
if(vis[u]) continue;//说明已经用过了，不再用
else vis[u]=1;
for(auto x:node[u])
{
int v=x.first,w=x.second;
if(d[u]+w<d[v]) {
d[v]=d[u]+w;
if(!vis[v]) q.push({-d[v],v});//为了存到v的最短距离，要多次入队，所以不能在这里标记vis
}
}
}
}
int main()
{
cin>>n>>m>>s;
int u,v,w;
forup(i,1,m){
cin>>u>>v>>w;
node[u].push_back({v,w});
}
memset(d,127,sizeof(d));//这个题的话这么赋值还要判一下，否则这么赋值还挺方便的。
dijkstra(s);
forup(i,1,n) cout<<d[i]<<' ';
return 0;
}