Weak Memory

题意：
给你一个n个点m条边的图，其中有k个节点是特殊的，起点s一定是特殊的，现在让你从s到t，每个特殊点可以加q点能量，经过一条边需要花费1点能量，求能从s到t时q最小为多少？（如果不能到达，输出-1）

思路：
求最小值，然后这值又具有单调性，所以可以二分枚举答案。
然后判断这个答案行不行可以用bfs（最好加优先队列优化）判断。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long

using namespace std;

const ll inf=1e9;
const int N=200005;

int ma[N], s, ti;
vector<int> g[N];

int vis[N];
struct p
{
    int v, t;
} p,p1;

bool operator<(struct p a,struct p b)
{
    a.t<b.t;
}

bool check(int d)
{
    memset(vis,-1,sizeof(vis));
    p.v=s;
    p.t=d;
    priority_queue<struct p> q;
    q.push(p);
    while(!q.empty())
    {
        p=q.top();
        q.pop();
        int v=p.v, t=p.t;
        if(t<=vis[v])
        {
            continue;
        }
        if(v==ti)
        {
            return 1;
        }
        vis[v]=max(vis[v],t);
        for(int i=0; i<g[v].size(); i++)
        {
            int u=g[v][i];
            if(t>0&&ma[u]==1&&d>vis[u])
            {
                p1.t=d;
                p1.v=u;
                q.push(p1);
            }
            else if(t-1>vis[u])
            {
                p1.t=t-1;
                p1.v=u;
                q.push(p1);
            }
        }
    }
    return 0;
}

int main()
{
    int n, m, K, k;
    scanf("%d%d%d",&n,&m,&K);
    for(int i=0; i<K; i++)
    {
        scanf("%d",&k);
        ma[k]=1;
    }
    for(int i=0; i<m; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    scanf("%d%d",&s,&ti);
    int l=0, r=N;
    while(r-l>1)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }
    if(r==N)
    {
        r=-1;
    }
    cout << r << endl;
    return 0;
}