这道水题水得有点吃力。。。

---

杨爷出的毒瘤数据。。。

首先是非负权图，就用dijkstra。

边比较稀疏，用堆优化。

再打模板的时候发现问题：

在去出堆顶元素的时候，可能会出现重复节点。

重复节点使用一个done数组进行标记，如果不给的话会跑得很慢。

然后图又可能不连通。。。数据的锅。

不连通的dist是\(2^{31} - 1\)。这个是锅。

代码：

#include
    
     #include
     
      #include
      
       const int maxn = 100005, maxm = 200005;struct Edges{    int next, to, weight;} e[maxm];int head[maxn], tot;int n, m, s;int dist[maxn];bool done[maxn];struct Nodes{    int v, w;    bool operator < (const Nodes &rhs) const    {        return w > rhs.w;    }};void link(int u, int v, int w){    e[++tot] = (Edges){head[u], v, w};    head[u] = tot;}int read(){    int ans = 0, s = 1;    char ch = getchar();    while(ch > '9' || ch < '0')    {        if(ch == '-') s = -1;        ch = getchar();    }    while(ch >= '0' && ch <= '9')    {        ans = ans * 10 + ch - '0';        ch = getchar();    }    return s * ans;}void dijkstra(){    memset(dist, 0x3f, sizeof(dist));    std::priority_queue
       
         q;    dist[s] = 0;    q.push((Nodes){s, dist[s]});    while(!q.empty())    {        Nodes x = q.top(); q.pop();        int u = x.v, dis = x.w;        if(done[u]) continue;        done[u] = true;        for(int i = head[u]; i; i = e[i].next)        {            int v = e[i].to;            if(dis + e[i].weight < dist[v])            {                dist[v] = dis + e[i].weight;                q.push((Nodes){v, dist[v]});            }        }    }}int main(){    n = read(), m = read(), s = read();    while(m--)    {        int u = read(), v = read(), w = read();        link(u, v, w);    }    dijkstra();    for(int i = 1; i <= n; i++)    {        printf("%d", dist[i]);        if(i != n) printf(" ");    }    printf("\n");    return 0;}