Ideal Path UVA - 1599

    这道题的坑是在普通BFS的基础上要查看最小权值。但是我一开始想着先用最普通的bfs来写，只是在初始化时做了一个权值的排序，然而并没有什么用，因为有可能：

但是一开始压进去的是b,它先找到e,所以这显然是错误的，所以应该转换一下思路，我们是因为不知道在第n层的最小权值应该是多少，才陷入困境，但是前提又是最短路，所以先从最后一个点开始bfs,其实这个思想是迪杰特斯特拉吧哈哈哈。然后我就醍醐灌顶了！既然都知道下一个点应该是什么，就找到那个有最小权值的点，压进去就好了。

#include <iostream>
#include <bits/stdc++.h>
#define maxn 100000+10
#define inf 0x3f3f3f
using namespace std;
int n,m;
vector<int>g[maxn];//点
vector<int>c[maxn];//颜色
int d[maxn];
int ans[maxn];//放置每一条上最小的颜色
bool vis[maxn];

void bfs1(int u)
{
    queue<int>q;
    q.push(u);
    vis[u] = 1;
    while(!q.empty())
    {
        int v = q.front();q.pop();
        if(v == 1) return;
        for(int i = 0;i<g[v].size();i++)
        {
            int w = g[v][i];
            if(!vis[w])
            {
                vis[w] = 1;
                d[w] = d[v]+1;
                q.push(w);
            }
        }
    }
}

void bfs2()
{
    queue<int>q;
    memset(vis,0,sizeof(vis));
    q.push(1);
    while(!q.empty())
    {
        int v = q.front();q.pop();
        if(v == n) return;
        for(int i = 0;i<g[v].size();i++)
        {
            int w = g[v][i];
            if(d[w] == d[v]-1)
            {
                ans[d[v]] = min(ans[d[v]],c[v][i]);
            }
        }
        for(int i = 0;i<g[v].size();i++)
        {
            int w = g[v][i];
            if(d[w] == d[v]-1 && c[v][i]==ans[d[v]] && !vis[w])
            {
                vis[w] = 1;
                q.push(w);
            }
        }
    }
}

int main()
{
    int a,b,k;
    while(cin>>n>>m)
    {
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        memset(ans,inf,sizeof(ans));
        for(int i = 1;i<=n;i++)
        {
            g[i].clear();
            c[i].clear();
        }
        for(int i = 0;i<m;i++)
        {
            cin>>a>>b>>k;
            g[a].push_back(b);
            g[b].push_back(a);
            c[a].push_back(k);
            c[b].push_back(k);
        }
        bfs1(n);
        bfs2();
        cout<<d[1]<<endl;
        cout<<ans[d[1]];
        for(int i = d[1]-1;i>0;i--)
            cout<<" "<<ans[i];
        cout<<endl;
    }
    return 0;
}
/**
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
**/