题意：
看白书
要点：
因为这次需要找字典序最小的边，所以以前随机打印的方法是不行的，这道题用了一个很巧妙的方法：先从终点倒着BFS，将所有结点到终点的最短步数储存起来，然后直接从起点开始走，再一次BFS，到达每一个新结点时要保证d值恰好-1，选择颜色字典序最小的走，如果有多个最小，就存入队列，下一次再比较新结点选择最小值。这道题还是挺难的，注意因为这题的数据比较大，所以直接用二维数组存储边是不行的，所以只能用两个不定长数组，分别存储互相连通的房间和颜色，互相对应。
#include#include #include #include #include using namespace std;#define INF 0x7fffffff //颜色的数据大1~10^9，必须0x7fffffff=2147483647>10^9才可以#define maxn 100010#define min(a,b) a>b?b:avector g[maxn]; //不定长数组用来存放互相连通的房间vector col[maxn]; //用来存放对应边的颜色int step[maxn]; //记录从n到i的最短步数int ans[maxn*2]; //记录经过的路径int vis[maxn]; int n, m;void init() //初始化{ for (int i = 0; i < maxn; i++) { g[i].clear(); col[i].clear(); } memset(step, -1, sizeof(step)); memset(ans, 0, sizeof(ans)); memset(vis, 0, sizeof(vis));}void bfs1() //从n开始将每个结点到末尾的最短步数记录下来{ queue q; step[n] = 0; q.push(n); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == 1) { step[v] = step[u] + 1; return; } if (step[v] == -1) { step[v] = step[u] + 1; q.push(v); } } }}void bfs2(){ queue q; q.push(1); while (!q.empty()) { int u = q.front(); q.pop(); if (!step[u]) //到达终点n return; int mmin = INF; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (step[v] == step[u] - 1) { mmin = min(col[u][i], mmin);//获得每步法颜色最小值 } } int temp_step = step[1] - step[u]; //从1到u的步数，也就是出发第temp_step步 if (ans[temp_step] == 0) ans[temp_step] = mmin; else ans[temp_step] = min(mmin, ans[temp_step]);//这里进行颜色大小相同时的比较，队列中此时会有多个，一个个比较取最小的那个 for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!vis[v] && step[v] == step[u] - 1 && mmin == col[u][i]) { vis[v] = 1;//vis重要，要判断是否走过，否则会超时 q.push(v); } } }}int main(){ int a, b,c; while (~scanf("%d%d", &n, &m)) { init(); while (m--) { scanf("%d%d%d", &a, &b, &c); if (a == b) continue; //如果两个结点相同直接弃掉，这条边没有用 g[a].push_back(b); g[b].push_back(a); col[a].push_back(c); col[b].push_back(c); } bfs1(); bfs2(); printf("%d\n", step[1]); for (int i = 0; i < step[1]; i++) { if (i) printf(" "); printf("%d", ans[i]); } printf("\n"); } return 0;}