Berland and the Shortest Paths CodeForces - 1005F（最短路树）

最短路树就是用bfs走一遍就可以了 d[v] = d[u] + 1 表示v是u的前驱边

然后遍历每个结点 存下它的前驱边 再用dfs遍历每个结点 依次取每个结点的某个前驱边即可

#include <bits/stdc++.h>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int maxn = 1e6+, INF = 0x7fffffff;

int n, m, k, cnt;

int head[maxn], d[maxn];

vector<int> f[maxn];

vector<string> g;

char str[maxn];

struct node

{

    int u, v, next;

}Node[maxn<<];

void add_(int u, int v)

{

    Node[cnt].u = u;

    Node[cnt].v = v;

    Node[cnt].next = head[u];

    head[u] = cnt++;

}

void add(int u, int v)

{

    add_(u, v);

    add_(v, u);

}

void init()

{

    mem(head, -);

    cnt = ;

}

void dfs(int u)

{

    if(g.size() >= k) return;

    if(u == n+) { g.push_back(str); return; }

    //cout<< 111 <<endl;

    for(int i=; i<f[u].size(); i++)

    {

        str[f[u][i]/] = '';

       // cout<< str <<endl;

        dfs(u+);

        str[f[u][i]/] = '';

    }

}

void bfs(int u)

{

    mem(d, -);

    queue<int> Q;

    Q.push(u);

    d[u] = ;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            node e = Node[i];

            if(d[e.v] == -)

            {

                d[e.v] = d[u] + ;

                Q.push(e.v);

            }

        }

    }

}

int main()

{

    init();

    int u, v;

    cin>> n >> m >> k;

    for(int i=; i<m; i++)

    {

        cin>> u >> v;

        add(u, v);

    }

    bfs();

   // cout<< 11 <<endl;

    for(int i=; i<=n; i++)

    {

        for(int j=head[i]; j!=-; j=Node[j].next)

            if(d[Node[j].v] +  == d[i])

            {

                f[i].push_back(j);

               // cout<< i << "  " << j/2 <<endl;

            }

    }

    for(int i=; i<m; i++) str[i] = '';

    dfs();

    cout<< g.size() <<endl;

    for(int i=; i<g.size(); i++)

    {

        cout<< g[i] <<endl;

    }

    return ;

}