每一个点跑一边Spfa复杂度显然是爆炸的
by Qiuly @ 2019-02-02 13:01:15
所以不妨建两个图，一个原图，一个反图，然后对两个图都跑一边Spfa，一样可以得出答案
by Qiuly @ 2019-02-02 13:02:12
比如说A*，在建立估值数组的时候，就是需要见反图跑spfa，因为我们要知道现在每个点到终点的距离。
同样的道理，现在我们要知道每个点到起点的距离，所以建反图再跑一次即可
by Qiuly @ 2019-02-02 13:04:00
这样的话复杂度只有 O(nk)
by Qiuly @ 2019-02-02 13:04:19
如果还过不了就换成 堆优Dij 吧。
by Qiuly @ 2019-02-02 13:05:03
@[maple666](/space/show?uid=85600)
by Qiuly @ 2019-02-02 13:05:12
堆优Dij 板子
```cpp
priority_queue<pair<int,int> > q;
inline void dijstra(){
F(i,n)dis[i]=inf;
dis[1]=0;q.push(make_pair(dis[1],1));
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x])continue;
vis[x]=true;
for(register int i=head[x];i!=0;i=edge[i].next){
int to=edge[i].to;
int w=edge[i].w;
if(dis[x]+w<dis[to]){
dis[to]=dis[x]+w;
q.push(make_pair(-dis[to],to));
}
}
}return;
}
```
by Qiuly @ 2019-02-02 13:09:29
@[Qiuly](/space/show?uid=113190) 蟹蟹神犇光环照耀！感谢大佬指教！
by maple666 @ 2019-02-02 13:12:22
@[Qiuly](/space/show?uid=113190) 我太蒻了，大佬指教一下怎么建反图呗
by maple666 @ 2019-02-02 13:19:35
```cpp
inline void add(int u,int v,int w){
G[1][++cnt[1]].nxt=head[1][u],G[1][cnt[1]].to=v,G[1][cnt[1]].val=w,head[1][u]=cnt[1];
G[2][++cnt[2]].nxt=head[2][v],G[2][cnt[2]].to=u,G[2][cnt[2]].val=w,head[2][v]=cnt[2];
}
```
其中 [1] 是正图，[2] 是反图
by Qiuly @ 2019-02-02 13:25:09