把路障看成智障的我, 笑了 5s 然后默然（MDZZ）qwq
昨天开到一个关于次短路和 k 短路的帖子，就拿 A* 去水了一下次短路，结果 luoguAC，LOJWA ， 。。。。你谷数据太水，都没照着题意写造一个最短路有多条的情况 ~~~
题目 ： Luogu
首先题目 哇一个裸的 $k$短路 qwq （NOIP 只会背板子选手，如果您会最短路求次短路…..qwq）
不过这题必须要 严格 k 短路 ，也就是第 k-1 短路可能有多条（不过数据水啊，不严格也行，要不是我在 LOJ 上面 WA 了，我都不知道要严格 qwq）
由于不会 k 短路的正解，只能靠着 A* 水水 qwq
如果您不会 A* 百度，google 上自学吧 qwq 或者您可以去 K 短路的板子那里学学 （不过那题 A$*$被卡了 qwq）
先上一个 A* 求 k 短路 的过程
算法过程：
- 将图反向，用 Dijstra+heap 求出 t 到所有点的最短距离，目的是求所有点到点 t 的最短路，用 dis[i] 表示 i 到 t 的最短路，其实这就是 $A*$的启发函数，显然：$h(n)
- 定义估价函数。我们定义 $g(n)$为从 s 到 n 所花费的代价，$h(n$) 为 $dis[n]$，显然这符合 $A*$算法的要求。
初始化状态。状态中存放当前到达的点 $i,f_i,g_i$。显然，$f_i=g_i+dis[i]$。初始状态为 $(S,dis[S],0)$，存入优先级队列中。
状态转移。假设当前状态所在的点 v 相邻的点 u，我们可以得到转换：$(V,fv,gv)$–>$(U,fu+w[v][u],gv+w[v][u])$。
终止条件。每个节点最多入队列 $K$次，当 $t$出队列 $K$次时，即找到解。
int n,m;
struct e{
int u,v,val;
}edge[maxn],edge_hx[maxn];//edge_hx 表示 求解的正向边 , edge[] 求 Dijkstra 的反向最短路
int head[maxn],tot,head_hx[maxn],toth;
void add(int u,int v,int val){
edge[++tot].v = v;
edge[tot].u = head[u];
head[u] = tot;
edge[tot].val = val;
edge_hx[++toth].v = v;//这题边是双向的所以建反边等于没说
edge_hx[toth].u = head_hx[u];
head_hx[u] = toth;
edge_hx[toth].val = val;
}
struct node{
int num,dis;
bool operator < (const node &ano) const{
return dis==ano.dis ? num > ano.num : dis > ano.dis;
}//Dijkstra 堆
};
priority_queue<node> q;//用于 Dijkstra
int dis[maxn];
void Dijkstra(int ed){
//就一个最短路
}
struct Node
{
int x,val;
bool operator< (const Node &a)const{
return val+dis[x] > a.val+dis[a.x];
}//用于计算优先队列 ， 估价函数 由于优先队列默认从大到小，所以重载也要反着来
};
priority_queue<Node>Q;//用于 A*
int cnt[maxn];//计算次数
int Astar(int st, int ed, int k){
Q.push( (Node){ st, 0} );
while( !Q.empty() ){
Node u= Q.top(); Q.pop();
++cnt[u.x];
if(cnt[u.x] == k && u.x == ed) return u.val;//如果出现次数为 k，且为重点的话，返回第 k 短路的值
if(cnt[u.x] > k) continue;
for(int i=head_hx[u.x];i;i=edge_hx[i].u){
int v= edge_hx[i].v, w= edge_hx[i].val;
Q.push((Node){v, u.val + w});//将每个状态加入优先队列
}
}
return -1;
}
int main()
{
n = read(),m=read();
fors(i,1,m){
int u = read(),v = read() , w = read();
add(u,v,w);
add(v,u,w);
}
int st=1, ed=n, k=2;//这里求第二短路
if( st==ed ) ++k;
Dijkstra(ed);
writen(Astar( st, ed, k ));
return 0;
}
你谷这题数据太水，上面的代码就可以 AC（70ms）
接着我们考虑 严格 k 短路 严格次短路我们就去掉重复的值（set！！）
使用 set 去重 ！！！每次当到达终点的时候就将值加入 set，判断 set 的 size == k 就可以了，给出完整代码 qwq（你也可以使用其他的一些东东 代替 set）
const int maxn = 2e5+7;
const int int_max = (1ll<<31)-1;
#define int_min = -int_max - 1;
const int mod = 1e8;
int n,m;
struct e{
int u,v,val;
}edge[maxn],edge_hx[maxn];
int head[maxn],tot,head_hx[maxn],toth;
void add(int u,int v,int val){
edge[++tot].v = v;//如果不是双向边，一定要反向啊 qwq
edge[tot].u = head[u];
head[u] = tot;
edge[tot].val = val;
edge_hx[++toth].v = v;
edge_hx[toth].u = head_hx[u];
head_hx[u] = toth;
edge_hx[toth].val = val;
}
struct node{
int num,dis;
bool operator < (const node &ano) const{
return dis==ano.dis ? num > ano.num : dis > ano.dis;
}
};
priority_queue<node> q;
int dis[maxn];
void Dijkstra(int ed){
memset(dis,127,sizeof dis);
dis[ed]=0;
q.push((node){ed,0});
while(!q.empty()){
node u=q.top();q.pop();
if(u.dis != dis[u.num]) continue;
for(int i=head[u.num];i;i=edge[i].u){
int v=edge[i].v;
if(dis[v] > u.dis+edge[i].val)
dis[v]=u.dis+edge[i].val,q.push((node){v,dis[v]});
}
}
}
struct Node
{
int x,val;
bool operator< (const Node &a)const{
return val+dis[x] > a.val+dis[a.x];
}
};
priority_queue<Node>Q;
set<int> dis_kth;
int Astar(int st, int ed, int k){
Q.push( (Node){ st, 0} );
while( !Q.empty() ){
Node u= Q.top(); Q.pop();
if(u.x == ed) dis_kth.insert(u.val);//如果到达终点就加到 set
if(k == dis_kth.size() && u.x == ed) return u.val;//大小相同并且是终点则直接返回这个值
if(dis_kth.size() > k) continue;
//如果大于 k 的话，就直接 continue
for(int i=head_hx[u.x];i;i=edge_hx[i].u){
int v= edge_hx[i].v, w= edge_hx[i].val;
Q.push((Node){v, u.val + w});
}
}
return -1;
}
int main()
{
n = read(),m=read();
fors(i,1,m){
int u = read(),v = read() , w = read();
add(u,v,w);
add(v,u,w);
}
int st=1, ed=n, k=2;//这里是 k = 2 短路
if( st==ed ) ++k;//st == ed 默认存在一条最短的边
Dijkstra(ed);
writen(Astar( st, ed, k ));
return 0;
}
0 条评论