关于 最短路 及其 拓展算法 的粗浅总结
最短路（Dijkstra）
Core_Code
inline void dijkstra()
{
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[s]=0;
priority_queue<pair<int,int> >q;
q.push(make_pair(dis[s],s));
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x])continue;
for(int i=head[x];i;i=E[i].nex)
{
int v=E[i].v;
if(dis[x]+E[i].w<dis[v])
{
dis[v]=dis[x]=E[i].w;
q.push(make_pair(-dis[v],v));
}
}
vis[x]=1;
}
}
正确性
不过多阐述了，只用简单的话讲讲我个人对这个算法的理解。
假设我们已经找到了所有的最短路，那么考虑对于一个节点 \(x\) ，其最短路 \(dis[x]\) 一定是从相邻的 \(v\) 的最短路 \(dis[v]\) 转移而来的，不难用反证法证得。言下之意，如果我们确定了当前的点的最短路 \(dis[now]\) ，那么我们就可以用 \(now\) 去更新周围的点，得到所有周围点 \(v\) 的 疑似 最短路，也就是我们所说的 松弛 操作 。之所以说是 疑似 ，是因为在这之后可能还会有其他的节点来对当前点 \(now\) 进行更新。
不难注意到，在对堆内元素进行枚举的时候，我们取出的 \(dis\) 序列是单调递增的，假设我们要求出 \(x\) 点的最短路，而 \(dis[x]\) 已经在优先队列中，那么所有可能对 \(dis[x]\) 进行更新的节点在优先队列中都位于它之前，当我们枚举到了 \(dis[x]\) 时，说明已经检查过了前面的节点是否会对它产生影响，那么这是他就一定是全局中的最短路，于是我们再用它对于之后的节点进行 松弛 ，之后再标记 \(vis[x]=1\) ，代表已经计算出它的最短路。用时间顺序表示如下：
检查之前的节点 \(\rightarrow\) 枚举到 \(x\) ，成功得到 \(dis[x]\) \(\rightarrow\) 用 \(x\) 去更新可能的 疑似 最短路。
扩展
分层最短路
常常用于有不同寻常的前行方式的变种最短路问题，用分层的方式来记录不同的状态。
过程类似于网络流的建模。
P4568 [JLOI2011] 飞行路线
最短路中有 \(K\) 次白嫖边权的机会，问此时的最短路是多少。
我们建 \(K\) 层图，初始位于最下面的一层，在常规建边的基础上，我们给每一条边一个向上一层的机会，也就是其中一个节点变为更高一层的节点，边权为 \(0\) 。这样就保证了一共可以上 \(K\) 层，也就是白嫖 \(K\) 次。
CF2014E
仍然是普通的最短路，但是到了某些节点之后（有马），就可以使得之后的前进过程都只消耗 \(w/2\) 的代价，并且是两个人同时出发，最后在一点汇合（可以停下等待）。
后者非常好解决，我们只需要跑两次最短路，然后枚举中间汇合的点就好了。
那么如何处理前者？就要用到分层最短路。
对于任何一个有马的节点，我们都向更高一层建一条边，而更高一层的所有边权都是底层对应的一半。最后的最短路就是两张图取一个 min 就行。
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int n,m,h;
struct Edge
{
int u,v,w,nex;
}e[2000010];
int tote,head[400010],vis[400010];
inline void add(int u,int v,int w)
{
e[++tote].u=u,e[tote].v=v,e[tote].w=w;
e[tote].nex=head[u],head[u]=tote;
}
struct Node
{
int x,dis;
};
bool operator <(Node a,Node b)
{
return a.dis>b.dis;
}
const int inf=1e15+1;
int dis1[400010],disn[400010];
inline void dj()
{
for(register int i=1;i<=2*n;++i)dis1[i]=inf,vis[i]=0;
dis1[1]=0;
priority_queue<Node> q;
q.push(Node{1,0});
while(q.size())
{
int x=q.top().x;q.pop();
if(vis[x])continue;
for(int i=head[x];i;i=e[i].nex)
{
int v=e[i].v,w=e[i].w;
if(dis1[x]+w<dis1[v])
{
dis1[v]=dis1[x]+w;
q.push(Node{v,dis1[v]});
}
}
vis[x]=1;
}
for(register int i=1;i<=2*n;++i)disn[i]=inf,vis[i]=0;
disn[n]=0;
priority_queue<Node> q1;
q1.push(Node{n,0});
while(q1.size())
{
int x=q1.top().x;q1.pop();
if(vis[x])continue;
for(int i=head[x];i;i=e[i].nex)
{
int v=e[i].v,w=e[i].w;
if(disn[x]+w<disn[v])
{
disn[v]=disn[x]+w;
q1.push(Node{v,disn[v]});
}
}
vis[x]=1;
}
}
inline void pre()
{
tote=0;
memset(head,0,sizeof(head));
re(n),re(m),re(h);
int tmp;
for(register int i=1;i<=h;++i)
{
re(tmp);
add(tmp,tmp+n,0);
}
for(register int i=1;i<=m;++i)
{
int u,v,w;
re(u),re(v),re(w);
add(u,v,w),add(v,u,w);
add(u+n,v+n,w/2),add(v+n,u+n,w/2);
}
dj();
// puts("display:");
// for(register int i=1;i<=n;++i)printf("%lld ",dis1[i]);
// printf("\n");
// for(register int i=1;i<=n;++i)printf("%lld ",disn[i]);
// printf("\n");
}
inline void solve()
{
int ans=1e15+2;
for(register int i=1;i<=n;++i)
{
if(dis1[i]==inf||disn[i]==inf)continue;
ans=min(ans,max(min(dis1[i],dis1[i+n]),min(disn[i],disn[i+n])));
}
if(ans==1e15+2)puts("-1");
else wr(ans),putchar('\n');
}
signed main()
{
int T;
cin>>T;
while(T--)
{
pre();
solve();
}
return 0;
}