【每日一题】2月25日Weak Memory

题意

主角PMP要搭车离开公园，有一个有n个节点m条边的无向图，PMP要从s走到t

因为主角PMP的记性不好，因此他需要志愿者的帮助，帮他找到路，PMP最多只能记住p距离的路线，志愿者总是会选择最好的路径，如果在p走不到时，会给他指向下一个在这条路径上的志愿者的位置，让我们求p的最小值

说实话这个地方我也看了很久，复述的也不太明白

直接说就是，有k个特殊的点，我记录从s到t的最短路径w，如果中间遇到了特殊节点，路径长度就清空w，那么这个w就是p的最小值

主要是题目没看懂，看懂了题目就很明白了，就是从起点出发，然后找最短路径，记录路径的长度，如果遇到了有志愿者的点，路径长度就清空为0 ，

用优先队列来实现，将与当前节点相连的路线放进优先队列，按照路线终点来排序（按照起点排序也行，起点排序跑的还更快），找到终点break即可，

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
#define pai pair<int, int>
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

struct node{
    int u , w;
    bool operator <(const node &a) const{
        return u < a.u;
    }
};

ll n , m , k;
vector<int>edge[N];
bool vis[N];
int s , t;
int dis[N];



int main(void){
    cin>>n>>m>>k;
    int x , u , v ,w;
    for(int i = 1 ; i <= k ; ++i){
        cin>>x;
        vis[x] = 1;
    }
    for(int i = 1 ; i <= m ; ++i){
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    cin>>s>>t;
    int ans = 0;
    memset(dis , 0x3f , sizeof(dis));
    priority_queue<pai , vector<pai> , greater<pai>> pq;
    pq.push({0 , s});
    while(pq.size()){
        w = pq.top().first , u = pq.top().second;
        pq.pop();
        ans = max(ans , w);
        if(u == t)  break;
        if(vis[u])  w = 0;
        for(auto& v : edge[u]){
            if(dis[v] > w + 1){
                dis[v] = w + 1;
                pq.push({dis[v] , v});
            }
        }
    }
    if(dis[t] == INF)   ans = -1;
    printf("%d\n" , ans);
    return 0;
}