[uva 1599] Ideal Path

题意：n个点m条边，可能有自环和重边的无向图，每条边上有一个数，求点1到点n字典序最小的最短路。多组数据。 从JY小朋友那里得知这道有趣的题目。

WC营员交流虽然基本没听懂什么......但学来一点，遇到一般图考虑一下生成树，尤其是DFS树和BFS树。

不带权的图的BFS树和最短路径树是一个东西。BFS树有一个特点：每一层的非树边只能连向同一层、上一层、下一层，否则就不是最短路径了。以点n为根建一棵BFS树，再从点1向根跑，只向上，就能获取点1到点n的所有最短路径，而且分好了层。贪心，每层只扩展字典序最小的边即可。

扩展的时候没对点去重，TLE一发。QAQ

把排序换成布尔数组，可以得到线性算法。不是通常那样扩展下一层时判重，而是本层的点不扩展两次，类似于优先队列实现的Dijkstra。

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5, MAX_M = 2e5, inf = (1<<30)-1;
struct Edge {
	int v, c;
	bool operator<(const Edge& rhs) const
	{
		return c < rhs.c;
	}
};
vector<Edge> adj[MAX_N+1];
int n, d[2][MAX_N+1], path[MAX_N];

void bfs(int s, int d[])
{
	queue<int> Q;
	Q.push(s);
	fill_n(d+1, n, inf);
	d[s] = 0;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i].v;
			if (d[v] == inf) {
				d[v] = d[u] + 1;
				Q.push(v);
			}
		}
	}
}

void build(int dis)
{
	static Edge e[MAX_M];
	static int q[MAX_N];
	q[0] = 1;
	int top = 1;
	for (int i = 0; i < dis; ++i) {
		int m = 0;
		while (top) {
			int u = q[--top];
			for (int k = 0; k < adj[u].size(); ++k) {
				int v = adj[u][k].v;
				if (d[0][v] == d[0][u]+1 && d[1][u] == d[1][v]+1)
					e[m++] = adj[u][k];
			}
		}
		int mn = inf;
		for (int j = 0; j < m; ++j)
			mn = min(mn, e[j].c);
		path[i] = mn;
		for (int j = 0; j < m; ++j)
			if (e[j].c == mn)
				q[top++] = e[j].v;
		sort(q, q+top);
		top = unique(q, q+top) - q;
	}
}

int main()
{
	int m;
	while (scanf("%d %d", &n, &m) == 2) {
		while (m--) {
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			adj[a].push_back((Edge){b, c});
			adj[b].push_back((Edge){a, c});
		}
		bfs(1, d[0]);
		bfs(n, d[1]);
		int dis = d[0][n];
		build(dis);
		printf("%d\n", dis);
		for (int i = 0; i < dis; ++i)
			printf("%d%c", path[i], " \n"[i == dis-1]);
		for (int i = 1; i <= n; ++i)
			adj[i].clear();
	}
	return 0;
}