前置知识

$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

4 4
5 2 5 4
1 2 2
1 3 5
2 3 4
3 4 2
1
4 3

输出样例1

7

数据范围与约定

对于全部数据，有 $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;
}

本题看似简单，直接输出$(1LL\lt\lt a+1LL\lt\lt b)$
但观察数据发现，$2^{63}+2^{63}=2^{64}$，而 long long 的最大值是 $2^{63}-1$ ，显然无法存下，即使使用 unsigned long long ，即$2^{64}-1$，也无济于事，因此，本题需要使用 __int128
__int128 是占用 $128$ 字节的整数存储类型，其范围是$-2^{127}$~$2^{127}-1$，在一定程度上可以取代高精度，实现起来也较高精度简单一些

当然，你也可以使用高精度解决，但就本题来说，使用 __int128 更为简单

需要注意，__int128 较普通的整数存储类型不同，不能直接使用cin/cout或scanf/printf输入输出，因此需要写函数读入
下面给出基础的读入，在别的题中使用时要注意判断负数及其他特殊情况(如果你想了解更多可以见实验舱2699题快速选择(链接)，题面给出了快读模版)

__int128 read()
{
    string str;
    cin>>str;
    __int128 res;
    for(int i=0;i<str.size();i++)
        res=res*10+str[i]-'0';
    return res;
}

剩下就是输出部分了，上文已经说过， __int128 无法使用输入输出，因此下面也给出递归输出模版：

void print(__int128 x)
{
    if(x==0)
        return;
    print(x/10)
    cout<<char(x%10+'0')//注意，即使是一位数 __int128 同样无法输出，因此需要强转char
}

有了 __int128 这样的工具，本题也不再困难，只需求出 $2^a$ 和 $2^b$ ,最后输出它们的和即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
__int128 a,b,A=1,B=1;

__int128 read(){
    string str;
    cin>>str;
    __int128 res=0;
    for(int i=0;i<str.size();i++)
        res=res*10+(str[i]-'0');//秦九韶算法，逐位读入
    return res;
}

void print(__int128 x){
    if(x==0)
        return;
    print(x/10);
    cout<<char(x%10+'0');
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif

    //使用函数读入数据
    a=read();
    b=read();
    for(int i=1;i<=a;i++)
        A*=2;
    for(int i=1;i<=b;i++)
        B*=2;
    print(A+B);//__int128数据用函数输出
    return 0;
}