https://codeforces.com/contest/59/problem/E
原来以为不会。。看了题解发现貌似自己其实是会的？
就是拆点最短路。。拆成n^2个点，每个点用(i,j)表示，表示这样的状态：原图中当前在j，前一步在i
然后就跑bfs，两点(i1,j1),(i2,j2)之前有边，当且仅当j1=i2，且(i1,j1,j2)没有被ban掉，且原图中(i2,j2)间有边；用一些set之类的来存储某三元组是否被ban
复杂度好像不是很对？然而仔细想一下可以发现转移最多总共只有O(nm)个，好像还行的样子
另外，在cf的数据上测出来这个方法跑的飞快（如果真的能卡满O(nm)还真的不一定能过?），不知道为什么
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<tr1/unordered_set>
#include<queue>
#include<set>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
struct pii
{
int fi,se;
};
bool operator==(const pii &a,const pii &b){return a.fi==b.fi&&a.se==b.se;}
struct H
{
inline size_t operator()(const pii &a) const
{
return unsigned(a.fi)*+a.se;
}
};
tr1::unordered_set<pii,H> s[];
struct E
{
int to,nxt;
}e[];
int f1[],ne;
pii pre[][];
int d[][];
int n,m,K;
queue<pii> q;
vector<int> an;
int main()
{
int i,x,y,z,u,v,k;pii t;
scanf("%d%d%d",&n,&m,&K);
for(i=;i<=m;++i)
{
scanf("%d%d",&x,&y);
e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne;
e[++ne].to=x;e[ne].nxt=f1[y];f1[y]=ne;
}
for(i=;i<=K;++i)
{
scanf("%d%d%d",&x,&y,&z);
s[x].insert((pii){y,z});
}
q.push((pii){,});d[][]=;
while(!q.empty())
{
t=q.front();q.pop();
u=t.se;
if(u==n)
{
printf("%d\n",d[t.fi][u]-);
//printf("1t%d %d\n",t.fi,u);
//printf("2t%d %d\n",pre[t.fi][u].fi,pre[t.fi][u].se);
for(x=t.fi,y=u;y;z=x,x=pre[x][y].fi,y=z)
an.pb(y);
for(i=an.size()-;i>=;--i)
printf("%d ",an[i]);
return ;
}
//printf("1t%d %d\n",t.fi,t.se);
for(k=f1[u];k;k=e[k].nxt)
{
v=e[k].to;
if(!d[u][v]&&!s[t.fi].count((pii){u,v}))
{
d[u][v]=d[t.fi][u]+;
pre[u][v]=t;
q.push((pii){u,v});
}
}
}
puts("-1");
return ;
}
https://www.luogu.org/problemnew/show/P1811
原题啊2333
不过没有spj，貌似必须把代码改成vector存边才能过
貌似放了一大堆假算法过去啊。。。