Spicy Restaurant 四川省赛 （BFS，线性规划）

Gym - 103117L

思路：

• 抓住spicy值的范围只有 100，从这里入手。（很关键）
• 利用线性规划的思路分2部做，优化时间复杂度和思维难度-- 先多源BFS 找到每一个点的以某个spicy值为目标的最短距离-- 然后在线性DP一下

#include 
using namespace std;
#define ri register int
#define M 100005

template <class G>void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
} 

int n,m,T;

vector <int> p[M];
int val[M];
int dis[105][M];
int inf;

void bfs(int c)
{
    queue<int>q;
    for(ri i=1;i<=n;i++)
    {
        if(val[i]==c)
        {
            q.push(i);
            dis[c][i]=0;
        }
    }
    while(!q.empty())
    {
        int a=q.front();q.pop();
        for(ri i=0;i)
        {
            int b=p[a][i];
            if(dis[c][b]!=inf) continue;
            dis[c][b]=dis[c][a]+1;
            q.push(b);
        }
    }
    
    
}
int main(){
    
    read(n);read(m);read(T);
    for(ri i=1;i<=n;i++)
    {
        read(val[i]);
    }
    for(ri i=1;i<=m;i++)
    {
        int a,b;
        read(a);read(b);
        p[a].push_back(b);
        p[b].push_back(a);
    }
    memset(dis,0x3f,sizeof(dis));
    inf = dis[0][0];
    
    for(ri i=1;i<=100;i++) bfs(i);
    for(ri i=1;i<=n;i++)
    for(ri j=2;j<=100;j++)
    {
        dis[j][i]=min(dis[j-1][i],dis[j][i]);
    }
    
    while(T--)
    {
        int a,b;
        read(a);read(b);
        if(dis[b][a]==inf) printf("-1\n");
        else 
        printf("%d\n",dis[b][a]);
    }
    return 0;
    
}