Ideal Path（UVA 1599）

网址如下：

Ideal Path - UVA 1599 - Virtual Judge (vjudge.net)

（第三方网站）

写了超久，最后是TLE，实在是累了，先总结一下吧

最后是对bfs有了个更深刻的理解

bfs相当于分层次进行分析处理，所以可以用队列来实现

如果想要将层次分开进行处理的话，可以用两个类似队列的东西（比如数组），然后分成两层判断，慢慢进行下去

我的代码主要是在寻找最小的颜色上花的时间很多

代码如下：

#include<cstdio>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<vector>
using namespace std;
struct Point{
    int d;
    map<int, int> p;
    map<int, set<int>> mclr;
    Point():d(0){}
};
void initialize(void);
void bfs1(void);
void bfs2(void);
const int maxn = 100001, maxclr = 1000000001;
int n, m, minstep;
Point pit[maxn];

int main(void)
{
    while(scanf("%d%d", &n, &m) == 2){
        initialize();
        for(int i = 0; i < m; i++){
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            pit[a].p[b] = c; pit[b].p[a] = c;
        }
        bfs1();
        bfs2();//同时输出
    }

    return 0;
}

void initialize(void)
{
    minstep = 2147483647;
    for(int i = 1; i <= n; i++){
        pit[i].d = 0; pit[i].p.clear();
    }
}
void bfs1(void)
{
    queue<int> q; q.push(n);
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(u == 1) minstep = pit[u].d;
        if(pit[u].d >= minstep) continue;
        for(auto v = pit[u].p.begin(); v != pit[u].p.end(); v++){
            if((*v).first != n && !pit[(*v).first].d){
                pit[(*v).first].d = pit[u].d + 1;
                pit[(*v).first].mclr[pit[u].d].insert(pit[(*v).first].p[u]);
                q.push((*v).first);
            }
        }
    }
}
void bfs2(void)
{
    printf("%d\n", minstep);
    vector<int> q; q.push_back(1);
    vector<int> ans; ans.resize(minstep, maxclr);
    while(!q.empty()){
        int minclr = maxclr, goalD = pit[q.front()].d - 1;
        for(auto it = q.begin(); it != q.end(); it++){
            int clr = *(pit[*it].mclr[goalD].begin());
            minclr = (minclr < clr) ? minclr : clr;
        }//得到当前层数到下一层的最小颜色
        ans[pit[q.front()].d - 1] = minclr;//储存答案
        if(!goalD) break;
        queue<int> tq;//下一层队列
        while(!q.empty()){
            int u = q.back(); q.pop_back();
            //将目标传到下一层队列
            for(auto it = pit[u].p.begin(); it != pit[u].p.end(); it++){
                if(pit[it->first].d == goalD && it->second == minclr) tq.push(it->first);
            }
        }
        //将下一层队列复制到当前队列中
        while(!tq.empty()){
            q.push_back(tq.front()); tq.pop();
        }
    }
    //输出
    while(minstep){
        printf("%d", ans[--minstep]);
        if(minstep) putchar(' ');
    }
    putchar('\n');
}