自动搬运

查看原文

来自洛谷，原作者为

	Fuko_Ibuki Niconiconi!

搬运于2025-08-24 21:30:35，当前版本为作者最后更新于2018-11-07 15:36:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Codeforces上有一道和这题题面一样并且有spj的题,如果你不幸被spj卡了可以去交一下.
Codeforces 59E Shortest Path
不过我这个代码没有spj也可以过. 据@hehe_54321大佬说题解的复杂度是假的,会被卡成指数级?
我用我的AC代码跑了一下大佬的数据,跑得飞快.
所以这是第一篇正确的题解?
我们考虑用边跑$bfs$.
以前我们写的$bfs$都是用点跑的,这一次我们用边跑.
为什么要用边跑?
这题中不能通过的三元组如果用点来跑$bfs$,非常难运用这个限制条件.
但是如果化边为点(~~线图(逃)~~思想),这些三元组就变成了不能从一个点走到另一个点,非常适合运用题目的条件了.
以上是@Styx大佬的思路,感谢他的高妙思路.
我们用$d[u][v]$表示从$(0\to 1)$(我们虚构的初始边)的边走到$(u\to v)$的这一条边所用的最少步数; 用$pre[u][v]=last$表示$u\to v$走过的前一条边是$last\to u$(由于边之间必须共点才算做有连边,因此$pre$只需要记录一个点,它指向的点藏在数组下标里).
用$vector$储存每个点连向哪些边,$set$存储不能走的三元组,$bfs$的时候$queue$里装$pair<int,int>$,表示当前搜索的点和这条边的另一个端点.
剩下的就在代码里说了.
(省略快读快写,大家肯定看得懂)

typedef pair<int,int> pii;
const int aoi=3058;
typedef int fuko[aoi][aoi];
fuko d,pre; 
vector<int> lj[aoi];
set<pii> ban[aoi];
int main() {
  int i,n,m,k,u,v,a;
  read(n),read(m),read(k);
  for (i=1;i<=m;++i) { // 加边
    read(u),read(v);
    lj[u].push_back(v);
    lj[v].push_back(u);
  }
  for (i=1;i<=k;++i) { 
    read(u),read(v),read(a);
    ban[u].insert(pii(v,a)); // 存储不能走的三元组
  }
  queue<pii> q; q.push(pii(1,0)); // 加入0->1 的边
  for (;!q.empty();) {
    pii now=q.front(); q.pop();
    int u=now.first,lat=now.second; // 表示当前的边是lat->u的,并且从u这个点向外扩展.
    if (u==n) { // u=n,标明有解并输出路径
      write(d[lat][n]),pl; // 注意u=n,就是到这条边的最短路长度.
      int stk[aoi<<5]={0},fa=n,tmp; 
      for (;;) {  // 接下来好好思考输出路径的方法
        stk[++*stk]=fa; // 当前走到的点.
        if (fa==1) break; // 到1了就跑
        tmp=lat,lat=pre[lat][fa],fa=tmp; 
        /*
        当前边是lat连向fa的,它的上一条边就应该是pre[lat][fa]连向lat的.
        所以这么往回跳.
        */
      }
      for (;*stk;--*stk) write(stk[*stk]),p32; 
      // 倒序输出并结束.解释一下,*stk=stk[0]
      return 0;
    }
    for (int v:lj[u]) {  // 遍历u能够到达的每一个点.
      if (!ban[lat].count(pii(u,v))&&!d[u][v]) { //lat->u->v的这个三元组没有被禁,并且u->v的这条边的距离也没有标记
        pre[u][v]=lat; // 标记pre
        d[u][v]=d[lat][u]+1; // 加距离
        q.push(pii(v,u)); // 推入队列
      }
    }
  }
  puts("-1"); // 无解.
}

谢谢大家.