题目：https://vjudge.net/problem/UVA-1599
思路：先反向做一次bfs，求出各点到终点经过的最少结点数量。然后正向做一次bfs，每次都选取颜色最小的路径，同时要保证距离的值刚好减1，如果有多条路可以走，则要记录这些结点，下一步需要考虑所有从这些点出发的边（这里的循环要注意写）
#include<cstdio>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
#define INF 1<<30
static const int MAX = 200500;int n,m;
vector<int> G[MAX]; //边
vector<int> C[MAX]; //从该点出发的颜色
int visit[MAX];
int length[MAX]; //length[i]表示结点i与终点的距离
int ans[MAX];//从终点往起点bfs,算出各点到点n最短距离
void reverse_bfs()
{memset(visit, 0, sizeof(visit));for (int i = 1; i <= n; i++)length[i] = INF;length[n] = 0;queue<int> Q;Q.push(n);visit[n] = 1;while (!Q.empty()){int v = Q.front(); Q.pop();for (int i = 0; i < G[v].size(); i++){int p = G[v][i];if (length[p] > length[v] + 1)length[p] = length[v] + 1;if (visit[p] == 0){visit[p] = 1;Q.push(p);}}}printf("%d\n", length[1]);
}//从起点往终点bfs,每次都选最小值
void bfs()
{for (int i = 0; i <= n; i++)ans[i] = INF;memset(visit, 0, sizeof(visit));set<int> S;S.insert(1);visit[1] = 1;while (!S.empty()){vector<int> tmp; //保存选择的结点int color = INF;int d = 0;//这次查找的结点距离终点的距离//选择颜色最小的结点for (set<int>::iterator it = S.begin(); it != S.end(); it++){d = length[*it];for (int i = 0; i < G[*it].size(); i++){if (length[*it] == length[G[*it][i]] + 1 && color > C[*it][i]){color = C[*it][i];tmp.clear(); tmp.push_back(G[*it][i]);}else if (length[*it] == length[G[*it][i]] + 1 && color == C[*it][i]){tmp.push_back(G[*it][i]);}}}if (d == 0) //已经到达终点break;ans[length[1] - d] = min(ans[length[1] - d], color);S.clear();for (vector<int>::iterator it = tmp.begin(); it != tmp.end(); it++){if (visit[*it] == 0){visit[*it] = 1;S.insert(*it);}}}for (int i = 0; i < length[1] - 1; i++)printf("%d ", ans[i]);printf("%d\n", ans[length[1] - 1]);
}int main()
{while (scanf("%d %d", &n, &m) != EOF){for (int i = 1; i <= n; i++){G[i].clear();C[i].clear();};for (int i = 0; i < m; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);if (a != b){G[a].push_back(b);G[b].push_back(a);C[a].push_back(c);C[b].push_back(c);}}reverse_bfs();bfs();}return 0;
}
