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)还真的不一定能过?），不知道为什么
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<tr1/unordered_set> 6 #include<queue> 7 #include<set> 8 using namespace std; 9 #define fi first 10 #define se second 11 #define mp make_pair 12 #define pb push_back 13 typedef long long ll; 14 typedef unsigned long long ull; 15 struct pii 16 { 17 int fi,se; 18 }; 19 bool operator==(const pii &a,const pii &b){return a.fi==b.fi&&a.se==b.se;} 20 struct H 21 { 22 inline size_t operator()(const pii &a) const 23 { 24 return unsigned(a.fi)*3527+a.se; 25 } 26 }; 27 tr1::unordered_set<pii,H> s[3010]; 28 struct E 29 { 30 int to,nxt; 31 }e[40010]; 32 int f1[3010],ne; 33 pii pre[3010][3010]; 34 int d[3010][3010]; 35 int n,m,K; 36 queue<pii> q; 37 vector<int> an; 38 int main() 39 { 40 int i,x,y,z,u,v,k;pii t; 41 scanf("%d%d%d",&n,&m,&K); 42 for(i=1;i<=m;++i) 43 { 44 scanf("%d%d",&x,&y); 45 e[++ne].to=y;e[ne].nxt=f1[x];f1[x]=ne; 46 e[++ne].to=x;e[ne].nxt=f1[y];f1[y]=ne; 47 } 48 for(i=1;i<=K;++i) 49 { 50 scanf("%d%d%d",&x,&y,&z); 51 s[x].insert((pii){y,z}); 52 } 53 q.push((pii){0,1});d[0][1]=1; 54 while(!q.empty()) 55 { 56 t=q.front();q.pop(); 57 u=t.se; 58 if(u==n) 59 { 60 printf("%d ",d[t.fi][u]-1); 61 //printf("1t%d %d ",t.fi,u); 62 //printf("2t%d %d ",pre[t.fi][u].fi,pre[t.fi][u].se); 63 for(x=t.fi,y=u;y;z=x,x=pre[x][y].fi,y=z) 64 an.pb(y); 65 for(i=an.size()-1;i>=0;--i) 66 printf("%d ",an[i]); 67 return 0; 68 } 69 //printf("1t%d %d ",t.fi,t.se); 70 for(k=f1[u];k;k=e[k].nxt) 71 { 72 v=e[k].to; 73 if(!d[u][v]&&!s[t.fi].count((pii){u,v})) 74 { 75 d[u][v]=d[t.fi][u]+1; 76 pre[u][v]=t; 77 q.push((pii){u,v}); 78 } 79 } 80 } 81 puts("-1"); 82 return 0; 83 }
https://www.luogu.org/problemnew/show/P1811
原题啊2333
不过没有spj，貌似必须把代码改成vector存边才能过
貌似放了一大堆假算法过去啊。。。