[图论紫书/Ch5] Ideal Path UVA - 1599 BFS/正向反向BFS

题目链接

先从终点BFS到起点,并记录下其到终点的距离,然后从起点BFS到终点,并优先选取边权值小的.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9+10;
const int maxn = 100005;

struct node
{
    int to;
    int col;
};

vector<node> mm[maxn];
int inque[maxn];
int d[maxn];
int vis[maxn];
int ans[maxn];
int n,m;


node nt;
struct poin
{
    int x;
    int step;
};


void bfs()
{
    //init inque ans d
    memset(inque,0,sizeof(inque));
    memset(d,0,sizeof(d));

    poin cur,nex;
    cur.step=0;
    cur.x=n;
    inque[n]=1;
    queue<poin> q;
    q.push(cur);

    while(!q.empty())
    {
        cur = q.front();
        q.pop();
        d[cur.x] = cur.step;


        if(cur.x==1) return ;

        int siz = mm[cur.x].size();
        for(int i=0;i<siz;i++)
        {
            if(!inque[mm[cur.x][i].to])
            {
                nex=cur;
                nex.step++;
                nex.x = mm[cur.x][i].to;
                inque[nex.x]=1;
                q.push(nex);
            }
        }
    }
}



void bfs1()
{
    //init vis and ans
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n+5;i++)
    {
        ans[i]=INF;
    }

    int cur=1,nex;

    queue<int> q;
    q.push(1);
    vis[1]=1;
    int minc=INF;
    while(!q.empty())
    {
        minc=INF;
        cur = q.front();
        q.pop();

        //find the minc
        int siz = mm[cur].size();
        for(int j=0;j<siz;j++)
        {
            nex = mm[cur][j].to;
            if(d[nex]+1==d[cur]&&inque[nex])
            {
                if(mm[cur][j].col<minc)
                {
                    minc=mm[cur][j].col;
                }
            }
        }

        //push the node of minc , the node should be pushed only once
        for(int j=0;j<siz;j++)
        {
            nex = mm[cur][j].to;
            if(d[nex]+1==d[cur]&&inque[nex]&&mm[cur][j].col==minc&&!vis[nex])
            {
                vis[nex]=1;
                q.push(nex);
            }
        }
//        cout <<"minc: "<< minc<<endl;
        int nowd = d[cur]-d[n];
//        cout << "nowd :"<<nowd<<endl;
        ans[nowd] = min(ans[nowd] , minc);
    }
}

int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
//    int T;
//    scanf("%d",&T);
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0;i<=n;i++)
            mm[i].clear();


        int u,v,col;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d",&u,&v,&col);

            if(u==v) continue;
            nt.to=v;
            nt.col=col;
            mm[u].push_back(nt);
            nt.to=u;
            nt.col=col;
            mm[v].push_back(nt);
        }

        bfs();
        bfs1();

        //output
        int siz = d[1];
        printf("%d\n",siz);
        for(int i=siz;i>=1;i--)
        {
            printf("%d",ans[i]);
            if(i!=1)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}