题解：P14726 [ICPC 2022 Seoul R] Forbidden Turns

· · 题解

睡不着起来写一道题。

思路：

本题最麻烦的一个地方在于可以重复经过一个结点。这意味着我们的 dis 数组不能按照原来的方式去定义。最开始我想的是按经过该点的次数，后来写炸了，就想到记一下这个结点的前驱结点，即从哪个结点走到这个结点。

实现就用 map 套 pair。pair 中存当前结点的前驱结点和当前结点。

接下来是怎么判断不合法的转弯。题目的意思大致是给你几个三元组 (x, y, z)，如果你前面从 x 号结点走到了 y 号结点，那么你的下一步就不能走到 z 这个结点。这个东西也可以用 map 来实现。像这样：

#define pii pair<int,int>
map<pii,set<int> > f;

这里的 pair 存 x 和 y。每次移动到下一个结点的时候就可以看一下移动到下一个结点合不合法。

跑完最短路我们遍历一遍 dis，看一下当前结点为 t 的答案取最小就行。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int ri=1e6+5;
bool vis[ri];
int n,m,k,s,t,head[ri],tot;
map<pii,set<int> > f; 
map<pii,int> dis;//dis[mp(u,v)]：走到v这个结点，前驱结点是u的最短距离 
struct edge{
    int nxt,to,val;
}e[ri];
struct node{
    int u,dis,pre;
    bool operator<(const node &t)const{
        return t.dis<dis;
    }
};
void add(int u,int v,int w){
    e[++tot]={head[u],v,w};
    head[u]=tot;
}
void dijkstra(int s){
    priority_queue<node> q; 
    q.push({s,0,-1});
    dis[mp(-1,s)]=0;//前驱结点初始化为-1（顶点编号 0-n-1） 
    while(q.size()){
        node t=q.top();
        q.pop();
        int u=t.u,pre=t.pre;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].val;
            if(f[mp(pre,u)].count(v)) continue;//pre->u->v 不合法 
            if(!dis.count(mp(u,v))||dis[mp(u,v)]>t.dis+w){//map不好初始化，所以要额外判一下是不是不存在 
                dis[mp(u,v)]=t.dis+w;
                q.push({v,dis[mp(u,v)],u});
            }
        } 
    }
}
int main(){
    scanf("%d%d%d%d%d",&m,&n,&k,&s,&t);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(int i=1,u,v,w;i<=k;i++){
        scanf("%d%d%d",&u,&v,&w);
        f[mp(u,v)].insert(w);//存不能转弯的边 
    }
    dijkstra(s);
    int ans=0x3f3f3f3f;
    for(auto [u,dis]:dis){
        if(u.second==t) ans=min(ans,dis);//统计走到t结点的全部方案取最优 
    }
    if(ans==0x3f3f3f3f){
        puts("-1");
        return 0;
    }
    printf("%d\n",ans);
    return 0;
}

::::

哪里讲的不清晰，或是不理解的可以在评论区问我。