题意简述

求字符串最短路。最短的定义有两种：

• 字典序最小。
• 长度最小，之后比较字典序。

知识点

最短路、贪心、拆点

解题思路

网格图 $n \leq 2000$

网格图下，所有 $1$ 到 $n$ 的路径长度都相同，因此两种定义下最短路是一致的。

考虑一个简单的贪心：当前走到一个点，其两条出边里选择字典序较小的那个。

这样的贪心在大部分情况下是正确的。不正确时，两条出边字典序一定相同。

对一个点，其最短路是可以确定的。因此我们转而维护每个点的最短路。注意，这样的话空间复杂度很差，只能跑 $2000$。

网格图

考虑优化。有的点永远不会成为最短路的一部分，因此考虑剪枝。对若干最短路长度相等的点，它们之中只有最短路字典序最小的若干个点可能成为最短路的一个前缀。

因此，我们维护当前字典序最小的路径，并维护有哪些点的最短路是它（我们称为有效点）。

转移：遍历所有有效点的所有出边，并取它们之中字典序最小的出边。只有这些出边的终点能成为下一时刻的有效点。注意要对有效点去重。

保证边权长度为 $1$

网格图的结论仍部分适用。

现在，一个点可以有很多出边，所以不去重很容易超时。去重也不能说就不超时了，以下分析复杂度：

每条边只会被遍历一次。证明：若一条边被遍历两次，说明一个点（这条边的起点）成为了有效点至少两次。这说明原图有环，不成立。

因此，总的遍历次数是 $O(m)$ 的。

与网格图的区别：两种最短路的定义不再等价。字典序最小仍然可以直接做；而保证路径最短就需要我们先跑两次常规最短路，求出 $1$ 到 $u$、$u$ 到 $n$ 的距离。之后，在取有效点时，要保证当前层数 + 到终点距离 = 起点到终点的最短距离。

保证边权长度为 $2$

也许可以考虑直接套用。

完整做法

边权长度不固定时，算法存在的漏洞是遍历出边时我们不知道哪条边是更优的。

因此，考虑拆点。利用中间点，把每条边权都变为一个字符，就仍然可以套用了。具体怎么变呢？考虑边 $(u, v, w)$，对每个 $w_i$，加边 $(p_i, p_{i+1}, w_i)$，其中 $p_1 = u, p_{|w|+1} = v$。

具体实现上，可以维护实际的总点数 nc，并在拆点时动态生成新的点。

标准代码

C++

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000005;

struct Edge {
  int u, v, next;
  char w;
} e[maxn << 1], f[maxn << 1];
vector<tuple<int, int, string>> E;
int head[maxn], cnt;
void add(int u, int v, char w) {
  e[++cnt].v = v;
  e[cnt].w = w;
  e[cnt].next = head[u];
  head[u] = cnt;
}
int headf[maxn], cntf;
void addf(int u, int v, char w) {
  f[++cntf].v = v;
  f[cntf].w = w;
  f[cntf].next = headf[u];
  headf[u] = cntf;
}

int n, m, nc;

void make_graph() {
  for (auto P : E) {
    int u = get<0>(P);
    int v = get<1>(P);
    string w = get<2>(P);
    int lst = u;
    for (int i = 0; i < w.length(); ++i) {
      int x = u, y = v;
      if (i != 0) x = lst;
      if (i != w.length() - 1) {
        y = lst = ++nc;
      }
      add(x, y, w[i]);
      addf(y, x, w[i]);
    }
  }
}

int dis1[maxn], disn[maxn];
void solve_dis1(int s) {
  queue<int> q;
  fill(dis1 + 1, dis1 + 1 + nc, 0x3f3f3f3f);
  dis1[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (dis1[v] > dis1[u] + 1) {
        dis1[v] = dis1[u] + 1;
        q.push(v);
      }
    }
  }
  return;
}
void solve_disn(int s) {
  queue<int> q;
  fill(disn + 1, disn + 1 + nc, 0x3f3f3f3f);
  disn[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = headf[u]; i; i = f[i].next) {
      int v = f[i].v;
      if (disn[v] > disn[u] + 1) {
        disn[v] = disn[u] + 1;
        q.push(v);
      }
    }
  }
  return;
}

bool vis[maxn];
string bfs(bool min_dis) {
  fill(vis, vis + maxn, false);
  string ans;
  vector<int> now, nxt;
  now.push_back(1);
  while (true) {
    char mn = 127;
    for (auto u : now) {
      for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (min_dis) if (ans.length() + disn[v] + 1 > dis1[n])
          continue;
        if (!min_dis) if (disn[v] >= 0x3f3f3f3f)
          continue;
        if (e[i].w < mn) {
          for (auto x : nxt) vis[x] = false;
          nxt.clear();
          mn = e[i].w;
          vis[v] = true;
          nxt.emplace_back(v);
        } else if (e[i].w == mn) {
          if (!vis[v]) {
            vis[v] = true;
            nxt.emplace_back(v);
          }
        }
      }
    }
    ans += mn;
    if (vis[n]) break;
    for (auto x : nxt) vis[x] = false;
    now.swap(nxt);
    nxt.clear();
  }
  return ans;
}

int main() {
  //freopen("path.in", "r", stdin);
  //freopen("path.out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    string w;
    cin >> u >> v >> w;
    E.emplace_back(u, v, w);
  }
  nc = n;
  make_graph();
  solve_dis1(1), solve_disn(n);
  cout << bfs(true) << ' ' << bfs(false) << endl;
  return 0;
}