洛谷 -【模板】单源最短路径（标准版） (堆优化 最短路dijkstra 链式存储)

题目链接
题目:


思路:
标准模板dij算法，但是普通的dij还是因为数据过大会TLE。
所以这里有一种优先队列的优化方法，使得时间复杂度再次降低。
详情代码注释

#include <bits/stdc++.h>
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 2e5 + 5;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
struct node
{
    int val;//这个边的权值
    int z;//子节点
    int Next;//从这个节点出发的其他节点的编号
}k[N];//链式存储存边
int Head[N],m,vis[N],dis[N],n,mm,s;
void Add(int a,int b,int c)
{
    mm++;
    k[mm].z = b;
    k[mm].val = c;
    k[mm].Next = Head[a];
    Head[a] = mm;
}//链式存储
struct Node
{
    int d;//距离
    int pos;//这个点
    bool operator <(const Node &a)const
    {
        return a.d < d;
    }//结构体内镶自动排序(配优先队列)
};//优先队列所用
void dij()
{
    priority_queue<Node> q;//优先队列，使得每次枚举最短的路径来更新边权值
    Node a;
    dis[s] = 0;
    q.push((Node){0,s});
    while(!q.empty())
    {
        a = q.top();
        q.pop();
        if(vis[a.pos]) continue;//如果这个点已经用过则不再枚举
        vis[a.pos] = 1;
        for(int i = Head[a.pos];i;i = k[i].Next)
        {
            if(dis[k[i].z] > dis[a.pos]+k[i].val)//如果从s到这个子节点的距离大于通过中间节点再到这个节点的值，更新最小值
            {
                dis[k[i].z] = dis[a.pos]+k[i].val;
                q.push((Node){dis[k[i].z],k[i].z});//因为有优先队列自动排序，所以这里直接q.push就行(会自动把目前的最短中间路径排到前面)
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> s;
    fill(dis,dis+N,INF);//先把所有的赋成无穷大
    for(int i = 0;i < m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        Add(a,b,c);
    }
    dij();
    for(int i = 1;i <= n;i++) cout << dis[i] << " ";
}