NOI.AC

前置知识

$1.$ 图论，图的存储和遍历
$2.$ 最短路算法Floyd

先看题面：

ty的社交

题目背景

$ty$ 每天都和妹纸打游戏，搁置了更新，导致 $SYC$ 的小朋友非常生气，但 $ty$ 还在悠闲地打游戏！

题目描述

$ty$ 可不会搭理催更这些话，今天他还是想和编号 $x$ 的妹纸打游戏，但和妹纸联机需要通信的时间，当然妹纸和妹纸之间也有可能有通信关系， $ty$ 也能通过妹纸联系另一名妹纸，现在告诉他们之间的通信关系， $ty$ 希望你告诉他和编号 $x$ 的妹纸联机需要多长时间，但挑剔的 $ty$ 不想通过魅力值低于 $q$ 的妹纸联系别人，他也不会和魅力值低于 $q$ 的妹纸玩。为了方便起见，我们将 $ty$ 编为一号。

输入格式

第一行 $n$ ， $m$ 表示有 $n$ 个妹纸，他们之间有 $m$ 条通信关系，下面一行 $n$ 个整数，表示每个妹纸的魅力值，接下来 $m$ 行，每行输入 $u$ ，$v$ 和 $w$ ，表示编号 $u$ 和 $v$ 之间通信需要 $w$ 的时间，接下来一个整数 $t$ ，表示 $t$ 组询问，下面 $t$ 行，每行两个整数 $x$ 和 $q$ ，表示 $ty$ 想和编号 $x$ 的妹纸打游戏，且不希望通过魅力值低于 $q$ 的妹纸联系别人。

输出格式

共 $t$ 行，每行一个整数表示 $ty$ 和编号 $x$ 的妹纸通信且不通过魅力值低于 $q$ 的妹纸需要的时间，若无解则输出-1。

输入样例1

输出样例1

数据范围与约定

对于全部数据，有 $1 \leq n , m \leq 100,1 \leq t \leq 15,1 \leq u , v , w , x \leq 100000,1 \leq q \leq 1000$

思路

将 $n$ 个妹纸， $m$ 条通信关系抽象成一个无向图，由于是求最短通信时间，因此做最短路。
可以看到 $n$ 的范围很小，仅到 $100$ ，适合使用 Floyd 。但发现与朴素 Floyd 不同，每个点需要其魅力值不小于 $q$ ，因此现将原图存入邻接表，每次 Floyd 初始化时判断两点魅力值是否都不小于 $q$ ，若满足，存入本次询问的图中，接着做朴素 Floyd 即可。

注意事项

~~三年OI一场空，不清多测见祖宗。~~
题目不保证无重边，存储图时注意取min

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,dp[205][205],x,y,q,z,a[105],g[105][105];
int main()
{
    memset(g,0x3f,sizeof g);
     cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    const ll inf=dp[0][0];
    for(int i=1;i<=n;i++)
        g[i][i]=0;//初始化
    while(m--)
    {
        cin>>x>>y>>z;
        g[x][y]=g[y][x]=min(g[x][y],z);//记得取min
    }
    cin>>t;
    while(t--)
    {
        cin>>x>>q;
        memset(dp,0x3f,sizeof dp);//记得清多测
        const ll inf=dp[0][0];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i]>=q&&a[j]>=q&&g[i][j])
                    dp[i][j]=dp[j][i]=g[i][j];//存下本次询问的可通行路径
       //朴素Floyd
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
        if(dp[1][x]==inf)//判断无解
            cout<<-1<<endl;
        else
            cout<<dp[1][x]<<endl;
    }
    return 0;
}