思路

1. Dijstra做法 + 链式前向星建图
2. 重边没有影响，正常建图就行

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int maxn = 2e6 + 5;
const int inf = 1e18;
int dis[maxn], vis[maxn], head[maxn];
int cnt = 0;
struct Edge
{
    int u, v, w, nxt;
}edge[maxn * 2];


int n = 0, m = 0, s = 0;


void AddEdge(int u, int v, int w)
{
    edge[++cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}


struct Node
{
    int v;
    int d;
    bool operator < (const Node &tmp) const
    {
        return d > tmp.d;
    }
    Node(int val, int dis) : v(val), d(dis) {}
};


std::priority_queue<Node> q;


void dij(int s)
{
    dis[s] = 0;
    q.push(Node(s, 0));
    while(!q.empty())
    {
        Node T = q.top();
        q.pop();
        int tmpv = T.v;
        if (vis[tmpv]) continue;
        vis[tmpv] = 1;
        for (int i = head[tmpv]; i != -1; i = edge[i].nxt)
        {
            if (dis[edge[i].v] > dis[tmpv] + edge[i].w)
            {
                dis[edge[i].v] = dis[tmpv] + edge[i].w;
                q.push(Node(edge[i].v, dis[edge[i].v]));
            }
        }
    }
}


void solve()
{
    for (int i = 0; i < maxn; i++)
    {
        head[i] = -1;
        vis[i] = 0;
        dis[i] = inf;
    }
    int u = 0, v = 0;
    std::cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v;
        AddEdge(u, v, 1);
    }
    dij(s);
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] != inf)
        {
            std::cout << dis[i] << " ";
        }
        else
        {
            std::cout << -1 << " ";
        }
    }
}


signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int t = 1;
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}