头像

空釉璃




离线:17小时前


最近来访(22)
用户头像
有恒
用户头像
沐星不仙了
用户头像
ZQCa
用户头像
L.妍ab
用户头像
狗头人挖土豆
用户头像
HH123_
用户头像
鱼香肉丝盖饭_6
用户头像
neepoo
用户头像
TLEmaker
用户头像
edgdcgxgbx
用户头像
WANGYAN
用户头像
封禁用户
用户头像
棒棒糖_5
用户头像
Sunflower
用户头像
早晴
用户头像
liuser
用户头像
WorrywartsL
用户头像
第一万零一次AC
用户头像
1908
用户头像
尼古拉斯小布丁


空釉璃
11天前

题目描述

一个序列中的“未排序”的度量是相对于彼此顺序不一致的条目对的数量,例如,在字母序列“DAABEC”中该度量为5,因为D大于其右边的4个字母,E大于其右边的1个字母。该度量称为该序列的逆序数。序列“AACEDGG”只有一个逆序对(E和D),它几乎被排好序了,而序列“ZWQM”有6个逆序对,它是未排序的,恰好是反序。
需要对若干个DNA序列(仅包含4个字母A、C、G和T的字符串)分类,注意是分类而不是按字母顺序排列,是按照“最多排序”到“最小排序”的顺序排列,所有DNA序列的长度都相同。

输入

第一行包括两个整数,n(0<n≤200)表示字符串长度,m(0<m≤200)表示字符串个数,两个数之间个一个空格;后面是m行,每行包括一个长度为n的字符串。

输出

按“最多排序”到“最少排序”的顺序输出所有字符串。若两个字符串的逆序对个数相同,按原始顺序输出它们!

样例输入

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

样例输出

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

思路:本题其实就是求每一个字符串的逆序对数目,然后根据逆序对数目进行排序,所以用归并排序对每一个字符串计算逆序对数目即可

#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 210;
typedef pair<int,int> pii;
string a[N];
pii sort_string[N];//存储不同逆序对和对应的字符串数组下标
int cnt = 0;
void merge(string &k,int l,int r)
{
    if(l >= r) return;
    int mid = l + r>>1;
    merge(k,l,mid),merge(k,mid+1,r);
    int i = l, j = mid+1;
    string temp;
    while(i <= mid && j <= r)
    {
        if(k[i] <= k[j]) temp  += k[i++];
        else{
            cnt += (mid - i + 1);
            temp  += k[j++];
        }
    }
    while(i <= mid) temp += k[i++];
    while(j <= r) temp += k[j++];
    for(i = 0, j = l; j <= r; i++, j++) k[j] = temp[i];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < m; i++)
        cin>>a[i];

    for(int i = 0; i < m; i++)
    {
        cnt = 0;
        string temp = a[i];
        merge(temp,0,n-1);
        sort_string[i].first = cnt;//得到当前序列的逆序对个数
        sort_string[i].second = i;
    }
    sort(sort_string,sort_string + m);
    for(int i = 0; i < m; i++)
    {
        int temp;
        temp = sort_string[i].second;
        cout<<a[temp]<<endl;
    }
    return 0;
}




空釉璃
11天前

题目描述

玩家根据骰子的点数决定走的步数,即骰子点数为1时可以走一步,点数为2时可以走两步,点数为n时可以走n步。求玩家走到第n步(n≤骰子最大点数且投骰子的方法唯一)时总共有多少种投骰子的方法。

输入

输入包括一个整数n(1≤n≤6)。

输出

输出一个整数,表示投骰子的方法数。

#include<iostream>
using namespace std;
int n,cnt;
void dfs(int k)
{
    if(k == n)
    {
        cnt++;
        return;
    }
    if(k > n) return;
    for(int i = 1; i <= 6; i++)
        dfs(k+i);
}
int main()
{
    cin>>n;
    dfs(0);
    cout<<cnt<<endl;
    return 0;
}



空釉璃
11天前

题目:

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。现在给出一个数字序列,允许使用一种转换操作:选择任意两个相邻的数,然后从序列移除这两个数,并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
对于所给序列要求出最少需要多少次操作可以将其变成回文序列。

输入

输入为两行,第一行为序列长度n ( 1 ≤ n ≤ 50),第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000),以空格分隔。

输出

输出一个数,表示最少需要的转换次数

样例输入

4
1 1 1 3

样例输出

2

#include<iostream>
using namespace std;
const int N = 55;
int cnt,min_step = 0x3f3f3f3f;
int a[N];
int n;
bool check(int k,int temp_check[])//判断是否回文串
{
    for(int i = 0; i < k; i++)
        if(temp_check[k - i - 1] != temp_check[i]) return false;
    return true;
}
bool dfs(int k,int a1[],int num)
{
    int temp[N];
    if(k == 0)  return false;
    if(check(k,a1)) 
    {
        min_step = min(min_step,num);//选择最小的
        return true;
    }
    for(int i = 0; i < k - 1; i ++)//选择哪一对 当前的数 
    {
        int sum = a1[i] + a1[i+1];//选择第i和第i+1个 加为和 
        int u = 0;
        for(int j = 0 ; j < k; j++)//把当前的情况放进到temp数组里面 
        {
            if(i == j)//如果遍历到了i的位置,就把和放进去
                temp[u++] = sum;
            else if(j == i+1) continue;//如果到了i+1,那么k++; 
            else temp[u++] = a1[j];
        }
        num ++;
        dfs(u,temp,num);
        num --;
    }
}
int main()
{
    cin>>n;
    cnt = n-1;
    for(int i = 0; i < n; i++)
        cin>>a[i];
    dfs(n,a,0);
    cout<<min_step<<endl;
    return 0;
}



空釉璃
17天前

在看提高课强连通分量的视频的时候,在想为什么拓扑排序的顺序是强联通分量的编号倒序,思想一番后得到以下结果,如有错误,请dalao们指出。

在tarjan求强连通分量中,其强连通分量的编号顺序是根据缩点后得到的拓扑排序从最后一个点到第一个点来排序的,因为在tarjan过程中,是在利用dfs进行遍历点,我们知道dfs在一棵树当中,是会遍历到最后一个叶结点,然后再回溯到其上面的根结点,所以是会先得到位于拓扑排序中的最后一个强连通分量,因此,在递推拓扑排序的时候需要从编号由大到小开始。




空釉璃
18天前

题目:

有一个整数序列,所有元素均不相同,设计一个算法求相差最小的元素对的个数。

代码

$O(n^2)$

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
int a[N] = {4,1,2,3};
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>a[i];
    int min_diff = 0x3f3f3f3f,cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
        {
            if(min_diff > abs(a[j] - a[i]))
            {
                min_diff = abs(a[j] - a[i]);
                cnt = 1;
            }
            else if(min_diff == abs(a[j] - a[i]))
                cnt ++;
        }
    cout<<cnt<<endl;
    return 0;
}

$O(nlogn)$

我们发现题目中说所有元素均不同,那么排序之后,当前元素与下一个元素的差 必定是 当前元素与其余元素差的最小值。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
int a[N] = {4,1,2,3};
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>a[i];
    sort(a,a+n);
    int min_diff = 0x3f3f3f3f,cnt = 0;
    for(int i = 0; i < n-1; i++)
        if(min_diff > abs(a[i+1] - a[i]))
        {
            min_diff = abs(a[i+1] - a[i]);
            cnt = 1;
        }
        else if(min_diff == abs(a[i+1] - a[i]))
            cnt ++;
    cout<<cnt<<endl;
    return 0;
}


活动打卡代码 AcWing 356. 次小生成树

空釉璃
30天前

暂时发现的问题是并没有遍历每条向上的边,所以导致环的最大边有问题,应该预处理中找


最后一个点过不去!不写了!

#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 100010, M = 3e5 + 10,inf = 0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
int cnt;
int p[N];//并查集
long long sum;//边权和
int q[N];//用来放bfs队列
int d1[N][17],d2[N][17];//放的是从j开始向上跳的点经过的最大边。
int depth[N];
int fa[N][17];
int n,m;
int d[N];
typedef long long ll;
struct Edge
{
    int a,b,w;
    bool used;
    bool operator < (const Edge &t) const{
        return w < t.w;
    }
}edge[M];
void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
void bfs()
{
    memset(depth,0x3f,sizeof depth);
    int hh = 0, tt = -1;
    q[++tt] = 1;
    depth[1] = 1;
    depth[0] = 0;
    fa[1][0] = 0;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] <= depth[t] + 1) continue;
            depth[j] = depth[t] + 1;
            q[++tt] = j;
            fa[j][0] = t;
            d1[j][0] = w[i],d2[j][0] = -inf;
            for(int k = 1; k <= 16; k++)
            {
                int mid = fa[j][k-1];
                fa[j][k] = fa[mid][k-1];
                int dist[4] = {d1[j][k-1],d2[j][k-1],d1[mid][k-1],d2[mid][k-1]}; 
                d1[j][k] = d2[j][k] = -inf;
                for(int u = 0; u < 4; u ++)
                {
                    int d = dist[u];
                    if(d > d1[j][k]) d2[j][k] = d, d1[j][k] = d;
                    else if(d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                }
            }
        }
    }
}

long long lca(int a,int b,int w)
{
    cnt = 0;
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 16 ; k >= 0; k --)
        if(depth[fa[a][k]] >= depth[b])
        {
            d[cnt++] = d1[a][k];
            d[cnt++] = d2[a][k];
            a = fa[a][k];
        }

    if(a != b)
    {
        for(int k = 16; k >= 0; k -- )
            if(fa[a][k] != fa[b][k])
            {
                d[cnt++] = d1[a][k];
                d[cnt++] = d2[a][k];
                d[cnt++] = d1[b][k];
                d[cnt++] = d2[b][k];
                a = fa[a][k];
                b = fa[b][k];
            }
        d[cnt++] = d1[a][0];
        d[cnt++] = d1[b][0];
    }
    int dist1 = -inf,dist2 = -inf;
    for (int i = 0; i < cnt; i ++ )
    {
        int temp = d[i];
        if (temp > dist1) dist2 = dist1, dist1 = temp;
        else if (temp != dist1 && temp > dist2) dist2 = temp;
    }

    //cout<<dist1 <<" "<<dist2<<endl;
    if (w != dist1)
        return w - dist1;
    return w - dist2;
}
// int find(int x) { return p[x] != x ? p[x] = find(p[x]) : p[x];}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void kruskal()
{
    sort(edge,edge+m);
    for(int i = 1; i <= n; i ++) p[i] = i;
    for(int i = 0; i < m; i++)
    {
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        a = find(a),b = find(b);
        if(a != b)
        {
            p[a] = b;
            sum += w;
            edge[i].used = true;//表示用过了
        }
    }
}
void build()
{
    memset(h,-1,sizeof h);
    for(int i = 0; i < m; i++)//建一图
    {
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        if(edge[i].used)//如果在最小生成树
        {
            add(a,b,w),add(b,a,w);
        }
    }
}
int main()
{

    cin>>n>>m;
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i] = {a,b,c};
    }

    kruskal();//找最小生成树
    build();
    bfs();

    long long ans = 1e18;
    for(int i = 0; i < m; i++)
    {
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        if(!edge[i].used)//不在最小生成树里面
        {
            ans = min(ans,sum + lca(a,b,w));//lca找到最大值
        }
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1171. 距离

空釉璃
30天前

倍增法

#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
const int N = 2e4 + 10, M = 2 * N;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int fa[N][17];
int depth[N];
bool st[N];
int q[N],qs[N];
int dist[N];
void add(int a,int b, int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    int tt = -1,hh = 0;
    q[++tt] = root;
    depth[root] = 1;
    depth[0] = 0;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                dist[j] = dist[t] + w[i];
                for(int k = 1; k <= 16; k++)
                    fa[j][k] = fa[fa[j][k-1]][k-1];
                q[++tt] = j;
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 16; k >= 0; k --)
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];

    if(a == b) return a;
    for(int k = 16; k >= 0; k --)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0; i < n-1; i ++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    bfs(1);
    for(int i = 1; i <= m; i ++)
    {
        int a,b;
        cin>>a>>b;
        int p = lca(a,b);
        cout<<dist[a] - dist[p] + dist[b] - dist[p]<<endl;
    }
    return 0;
}

tarjan法

#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<vector>
using namespace std;
const int N = 4e4+10, M = 2 * N;
typedef pair<int,int> pii;
int h[N],ne[M],e[M],w[M],idx;
vector<pii> q[N];//存放点
int dist[N];
int st[N];
int res[M];
int p[N];
void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void tarjan(int u)
{
    st[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        tarjan(j);
        p[j] = u;
    }

    for(auto item : q[u])
    {
        int a = item.first,id = item.second;
        if(st[a] == 2)
        {
            int temp = find(a);
            res[id] = dist[u] + dist[a] - 2*dist[temp];
        }
    }
    st[u] = 2;
}
void dfs(int u,int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j,u);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0; i < n-1; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i = 1; i <= m; i ++)
    {
        int a,b;
        cin>>a>>b;
        if(a != b)
        {
            q[a].push_back({b,i});
            q[b].push_back({a,i});
        }
    }
    for(int i = 1; i <= n; i++) p[i] = i;
    dfs(1,-1);
    tarjan(1);
    for(int i=1;i<=m;i++)cout << res[i]<<endl;
    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

空釉璃
30天前

解释一下depth[0] = 0;因为在倍增过程中,可能会跳出根节点的上面,而如果按照初始设定为0x3f的话,那在lca中会认为当前的深度depth还是大于另一个点的深度,所以会继续向上跳,但其实已经跳出了根节点的范围了,所以要设depth[0]为0,同时设root的父节点为0,这样就可以不会导致深度跳过头了。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N = 4e4 + 10,M = 2 * N;
int h[N],e[M],ne[M],idx;
int n,m;
int p[N],depth[N],fa[N][17];
int q[N];
bool st[N];
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    int tt = -1, hh = 0;
    q[++tt] = root;
    st[root] = true;
    depth[root] = 1;
    depth[0] = 0;//防止当lca中fa到了根节点后,如果为0x3f可能会导致继续向上找结点的意外
    fa[root][0] = 0;//根结点没有父节点
    while(hh <= tt)
    {
        int t = q[hh++];
        st[t] = true;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(st[j]) continue;
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                for(int k = 1; k <= 16; k ++)
                    fa[j][k] = fa[fa[j][k-1]][k-1];
                q[++tt] = j;
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 16; k >= 0; k -- )
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if(a == b) return a;
    for(int k = 15; k >= 0; k -- )
    {
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];

}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    int root = 0;
    for(int i = 0; i < n; i++)
    {
        int a,b;
        cin>>a>>b;
        if(b == -1) root = a;
        else add(a,b), add(b,a);
    }
    bfs(root);
    cin>>m;
    for(int i = 0; i < m; i++)
    {
        int a,b;
        cin>>a>>b;
        int p = lca(a,b);
        if(p == a) puts("1");
        else if(p == b) puts("2");
        else puts("0");
    }

    return 0;
}


活动打卡代码 AcWing 393. 雇佣收银员

空釉璃
30天前

这道题的s24,竟然是可以和0建边的
因为s24 = c -> s24 - s0 = c -> s24 = c + s0
那两边迫敛后:
s24 >= c + s0 , s0 >= s24 - c, 所以可以用来建边

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010,M = 2 * N;
int dist[N],q[N],cnt[N];
bool st[N];
int h[N],e[M],ne[M],w[M],idx;
int r[N];
int k[N];
int n;
void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
void build(int s24)
{
    add(0, 24, s24), add(24, 0, -s24);
    for(int i = 1; i <= 24; i ++)
    {
        if(i < 8) add(16+i,i,r[i] - s24);
        else add(i-8,i,r[i]);
    }
}
bool spfa()
{
    memset(dist,-0x3f,sizeof dist);
    memset(st,false,sizeof st);
    memset(cnt,0,sizeof cnt);
    int tt = 0, hh = 0;
    dist[0] = 0;
    q[tt++] = 0;
    cnt[0] = 1;
    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= 25) return false;
                if(!st[t])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return true;
}
int main()
{
    int t;
    cin>>t;
    while(t --)
    {
        memset(k,0,sizeof k);
        for(int i = 1; i <= 24; i ++)   cin>>r[i];
        cin>>n;
        for(int i = 0; i < n; i ++)
        {
            int a;
            cin>>a;
            k[a+1] ++;
        }
        bool p = false;
        for(int i = 0; i <= 1000; i++)
        {
            memset(h,-1,sizeof h);
            idx = 0;
            for(int i = 1; i <= 24; i++)    add(i-1,i,0),add(i,i-1,-k[i]);
            build(i);
            p = spfa();
            if(p)
            {
                cout<<i<<endl;
                break;
            }
        }
        if(!p) puts("No Solution");

    }
    return 0;
}


活动打卡代码 AcWing 1170. 排队布局

空釉璃
1个月前
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010, M = 2 * N,inf = 0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
int q[N];
int dist[N];
int cnt[N];
bool st[N];
int n,ml,md;
void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
bool spfa(int size)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    int tt = 0,hh = 0;
    for(int i = 1; i <= size; i++)
    {
        q[tt++] = i;
        dist[i] = 0;
        st[i] = true;

    }
    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] > n + 1) return false;
                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return true;
}
int main()
{
    cin>>n>>ml>>md;
    memset(h,-1,sizeof h);
    for(int i = 0; i < ml; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a > b) swap(a,b);
        add(a,b,c);
    }
    for(int i = 0; i < md; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a > b) swap(a,b);
        add(b,a,-c);
    }
    for(int i = 1; i < n; i++)
    {
        add(i+1,i,0);
    }
    if(!spfa(n)) puts("-1");
    else{
        int p = spfa(1);
        if(dist[n] >= inf /2 ) puts("-2");
        else cout<<dist[n]<<endl;
    }
    return 0;
}