分析：出题人丧心病狂卡spfa......只能用dijkstar+堆优化.
主要的难点是字典序的处理上，一个想法是在做最短路的时候处理，边松弛边记录，比个大小记录最佳答案.具体的思路大概和最短路计数差不多，当遇到d[u] + w[i] == d[v]是，说明到d[v]有两条最短路了，更新一下答案。
但是这样效率太低了，每一次松弛都要更新一次，能不能一次性更新完呢？可以的.我们在跑完最短路后把满足d[u] + w[i] == d[v]的点v加入u的邻接表中，排个序，然后dfs一遍就好了.
#include#include #include #include #include #include #include #include using namespace std;const long long inf = 1e15;struct node{ long long len; int x;};bool operator < (node a, node b){ return a.len > b.len;}int n, m,b[200010],head[200010],to[400010],nextt[400010],tot = 1,w[400010],vis[200010];int u[400010], v[400010], z[400010],ans[200010];long long d[200010];vector a[200010];void add(int x, int y, int z){ w[tot] = z; to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}void dijkstar(){ d[1] = 0; priority_queue q; node t; t.len = 0; t.x = 1; q.push(t); while (!q.empty()) { while (!q.empty() && vis[q.top().x]) q.pop(); if (q.empty()) break; node u = q.top(); q.pop(); long long len = u.len; int x = u.x; vis[x] = 1; for (int i = head[x]; i;i = nextt[i]) { int v = to[i]; if (len + w[i] < d[v]) { d[v] = len + w[i]; node temp; temp.len = d[v]; temp.x = v; q.push(temp); } } }}bool cmp(int x, int y){ return b[x] < b[y];}void dfs(int depth, int x){ if (vis[x]) return; vis[x] = 1; ans[depth] = x; if (x == n) { for (int i = 1; i <= depth; i++) printf("%d ", b[ans[i]]); printf("\n"); return; } for (int i = 0; i < a[x].size(); i++) dfs(depth + 1, a[x][i]);}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u[i], &v[i], &z[i]); add(u[i], v[i], z[i]); } for (int i = 1; i <= n; i++) d[i] = inf; dijkstar(); printf("%lld\n", d[n]); for (int i = 1; i <= m; i++) if (d[u[i]] + z[i] == d[v[i]]) a[u[i]].push_back(v[i]); for (int i = 1; i <= n; i++) sort(a[i].begin(), a[i].end(), cmp); memset(vis, 0, sizeof(vis)); dfs(1, 1); return 0;}