关于dijkstra+堆过了标准版但没过弱化版。

#include <iostream>
#include <queue> //使用小根堆维护
#define big long long
using namespace std;
big n,m,s,cnt=0;
big a,b,v;
big getto[200005],value[200005],nxt[200005],point[100005];
big dis[100005],vis[100005];
struct Node{
    big val,point;
    friend bool operator < (Node l,Node r)
    {
        return l.val > r.val;
    }//以 dis_i 为关键字排序
}tmp;
priority_queue <Node> q;//使用小根堆维护。
void build(big a,big b,big v)
{
    cnt++;
    getto[cnt] = b;
    value[cnt] = v;
    nxt[cnt] = point[a];
    point[a] = cnt;
}//链式前向星
void dijkstra()
{
    for(big i = 1;i <= n;i++)//初始化
    {
        dis[i] = 2147483647;
    }
    dis[s] = 0;//起点最短路为0。
    tmp.point = s;
    tmp.val = 0;
    q.push(tmp);
    while(!q.empty())
    {
        big u = q.top().point;//已经进行小根堆维护，直接找到最小点。
        
        q.pop();//下一次不需要处理该点。
        if(vis[u])
        {
            continue;
        }//处理过，寻找下一个。
        vis[u] = 1;//找到点，标记为走过。
        for(big i = point[u];i ;i = nxt[i])//遍历所有 u -> i。
        {
            if(dis[getto[i]] > dis[u]+value[i])//目前到 u 的最短路+value[u -> i] < 目前到 i 的最短路（松弛操作）
            {
                dis[getto[i]] = dis[u]+value[i]; //更新最短路
                tmp.val = dis[getto[i]];
                tmp.point = getto[i];
                q.push(tmp);//更新堆，重新排序。
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for(big i = 1;i <= m;i++)
    {
        scanf("%lld %lld %lld",&a,&b,&v);
        build(a,b,v);
    }
    dijkstra();
    for(big i = 1;i <= n;i++)
    {
        printf("%lld ",dis[i]);
    }
    return 0;
}// O(n^2 + m) => O(m log_m)
//单元最短路径（弱化版）