题解 P1811 【最短路_NOI导刊2011提高（01）】

· · 题解

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"); // 无解.
}

谢谢大家.