题解 | #【模板】单源最短路Ⅰ ‖ 无权图#

注意题目是有向图。

#include<bits/stdc++.h>
// #define int long long
#define double long double
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII;
const int N=2e6+10;
const int M=1e3+10;
int mod=1e9+7;
int dist[N];
vector<int> adj[N];
int vis[N];
void bfs(int sx){
    queue<PII> q;
    q.push({sx,0});
    dist[sx]=0;
    while(!q.empty()){
        int u=q.front().first;
        int d=q.front().second;
       q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        dist[u]=d; 
        for(int v:adj[u]){
            if(!vis[v]){
                q.push({v,d+1});
            }
        }
    }
}

void solve(){
    int n,m,st;
    cin>>n>>m>>st;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }   
    bfs(st);
    for(int i=1;i<=n;i++){
        if(!vis[i]) cout<<-1<<" ";
        else cout<<dist[i]<<" ";
    }
}

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