题解：CF59E Shortest Path

对于 $k$ 对有序的三元组 $(x,y,z)$ 为不能走的路线。本题对选择恰当的工具存储三元组有着较高的要求。

首先想到的是 map 与 set，令 set <int> ban[x][y] 记录形如 $x \to y \to z_i$ 的所有 $z_i$。进行广度优先搜索，记录一个点 $u$ 的前驱 $p$ 点的同时遍历后继节点 $v$，若 $(u,v,z)$ 合法，即 ban[x][y].find (z) == ban[x][y].end ()，同时该路径可以更新，那么加入队列中去并记录下前驱节点（用于路径的输出）。于是得到了以下核心代码：

set <int> ban[MAX][MAX];
void bfs ()
{
    q.push ({0,1});
    while (!q.empty ())
    {
        pair <int,int> x = q.front ();q.pop ();
        int p = x.first,u = x.second;
        if (u == n)
        {
            printf ("%d\n",dis[p][u]);
            print (p,u);
            ok = 1;puts ("");
            return ;
        }
        for (auto v : ve[u])
        {
            if (ban[p][u].find (v) == ban[p][u].end () && !dis[u][v])
            {
                pre[u][v] = p;dis[u][v] = dis[p][u] + 1;
                q.push ({u,v});
            }
        }
    }
}

虽然能过样例，可是……一交发现 $\texttt{MLE}$。仔细一看 $k$ 的范围，直接寄。于是尝试用哈希来优化空间。大体思路相同，而这次用 $xyz+x+y+z$ 对大质数 $p$ 的值来表示 $(x,y,z)$，考虑到重复，用 vector <tri> hsh[M] 来记录同一个值的不同三元组，这样空间便可大大降低，可以通过此题。代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 3005;
const int M = 999983;
const int MOD = 1e9 + 7;
inline int read ();
struct tri
{
    int x,y,z;
};
int n,m,k,ok,dis[MAX][MAX],pre[MAX][MAX];
vector <int> ve[MAX];
vector <tri> hsh[M];
queue <pair <int,int> > q;
int get (int x,int y,int z);
void add (int u,int v);
bool check (int x,int y,int z);
void bfs ();
void print (int u,int v);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();m = read ();k = read ();
    for (int i = 1;i <= m;++i)
    {
        int x = read (),y = read ();
        ve[x].push_back (y);ve[y].push_back (x);
    } 
    for (int i = 1;i <= k;++i)
    {
        int x = read (),y = read (),z = read ();
        hsh[get (x,y,z)].push_back ((tri){x,y,z});
    }
    bfs ();
    if (!ok) puts ("-1");
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
int get (int x,int y,int z)//进行哈希操作
{
    return (1ll * x * y * z % M + 1ll * x + 1ll * y + 1ll * z) % M;
}
bool check (int x,int y,int z)//检测是否合法
{
    for (auto tmp : hsh[get (x,y,z)])
        if (tmp.x == x && tmp.y == y && tmp.z == z) return 1;
    return 0;
}
void bfs ()
{
    q.push ({0,1});
    while (!q.empty ())
    {
        pair <int,int> x = q.front ();q.pop ();
        int p = x.first,u = x.second;
        if (u == n)
        {
            printf ("%d\n",dis[p][u]);//输出路径长度
            print (p,u);
            ok = 1;puts ("");
            return ;
        }
        for (auto v : ve[u])
        {
            if (!check (p,u,v) && !dis[u][v])//合法且能过更新
            {
                pre[u][v] = p;dis[u][v] = dis[p][u] + 1;
                q.push ({u,v});
            }
        }
    }
}
void print (int u,int v)// 递归输出路径
{
    if (!v) return ;//终止条件
    print (pre[u][v],u);
    printf ("%d ",v);
}