头像

不止步于此

关注数
3
粉丝数
3
阅读量
3780


离线：4小时前

最近来访(39)
用户头像
Afterglow_0
用户头像
yxc的小迷妹
用户头像
Fir_0
用户头像
辣鸡号航母
用户头像
雷霆尬拔
用户头像
玄静
用户头像
清风qwq
用户头像
StkOvflow
用户头像
诺诺
用户头像
李菜菜想变强
用户头像
L-L
用户头像
峰哥
用户头像
一人舛木
用户头像
孤傲
用户头像
SC_Ning
用户头像
violet_garden
用户头像
老王爱吃面
用户头像
henrychenOutlook
用户头像
Mellina
用户头像
L._517

活动打卡代码 AcWing 903. 昂贵的聘礼
不止步于此的头像
不止步于此
4小时前 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110,INF = 0x3f3f3f3f;

int m,n;
int w[N][N],level[N];
int dist[N];
bool st[N];

int dijkstra(int down,int up)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);

    dist[0] = 0;

    for( int i = 1 ; i <= n ; i ++ )
    {
        int t = -1;
        for( int j = 0 ; j <= n ; j ++ )
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        for( int j = 0 ; j <= n ; j ++ )
            if(level[j] >= down && level[j] <= up)
                dist[j] = min(dist[j] , dist[t] + w[t][j]);
    }

    return dist[1];
}

int main()
{
    scanf("%d%d",&m,&n);

    memset(w,0x3f,sizeof w);
    for( int i = 0 ; i <= n ; i ++ ) w[i][i] = 0;

    for( int i = 1 ; i <= n ; i ++ )
    {
        int p,l,x;
        scanf("%d%d%d",&p,&l,&x);
        w[0][i] = min(w[0][i] , p);
        level[i] = l;

        for( int j = 1 ; j <= x ; j ++ )
        {
            int t,v;
            scanf("%d%d",&t,&v);
            w[t][i] = min(w[t][i] , v);
        }
    }

    int res = INF;
    for( int i = level[1] - m ; i <= level[1] ; i ++ ) res = min(res , dijkstra(i , i + m));

    printf("%d",res);

    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 920. 最优乘车
不止步于此的头像
不止步于此
18小时前

新的建图思路以及复杂的读入方式

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<sstream>
using namespace std;

const int N = 510;

int m,n;
int g[N][N];
int dist[N];
int stop[N];
int q[N];

void bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    int hh = 0,tt = 0;
    q[0] = 1;

    while( hh <= tt )
    {
        int t = q[hh++];

        for( int i = 1 ; i <= n ; i ++ )
            if(g[t][i] && dist[i] > dist[t] + 1)
            {
                dist[i] = dist[t] + 1;
                q[++tt] = i;
            }
    }
}

int main()
{
    scanf("%d%d",&m,&n);

    string line;
    getline(cin , line);

    while( m -- )
    {
        getline(cin , line);
        stringstream ssin(line);

        int cnt = 0,p;
        while(ssin >> p) stop[cnt++] = p;
        for( int i = 0 ; i < cnt ; i ++ )
            for( int j = i + 1 ; j < cnt ; j ++ )
                g[stop[i]][stop[j]] = 1;
    }

    bfs();

    if(dist[n] == 0x3f3f3f3f) printf("NO");
    else printf("%d",dist[n] - 1);

    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 1126. 最小花费
不止步于此的头像
不止步于此
1天前 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2010;
int n,m;
double g[N][N],dist[N];
bool st[N];

void dijkstra(int S)
{
    dist[S] = 1;

    for( int i = 1 ; i < n ; i ++ )
    {
        int t = -1;
        for( int j = 1 ; j <= n ; j ++ )
        {
            if(!st[j] && (t == -1 || dist[j] > dist[t]))
                t = j;
        }

        st[t] = true;

        for( int j = 1 ; j <= n ; j ++ )
        {
            dist[j] = max(dist[j] , dist[t] * g[t][j]);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    while( m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        double z = (100.0 - c) / 100;
        g[a][b] = g[b][a] = max(g[a][b] , z);
    }

    int S,T;
    scanf("%d%d",&S,&T);

    dijkstra(S);

    printf("%.8lf",100 / dist[T]);

    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 1127. 香甜的黄油
不止步于此的头像
不止步于此
2天前 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 810,M = 3000,INF = 0x3f3f3f3f;
int n,p,m;
int id[N];
int h[N],e[M],w[M],ne[M],idx;
int dist[N],q[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

int spfa(int u)
{
    memset(dist,0x3f,sizeof dist);
    dist[u] = 0;

    int hh = 0,tt = 1;
    q[0] = u;
    st[u] = true;

    while( hh != tt )
    {
        int t = q[hh++];
        if(hh > N) hh = 0;
        st[t] = false;

        for( int i = h[t] ; i != -1 ; i = ne[i] )
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt > N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    int res = 0;
    for( int i = 1 ; i <= n ; i ++ )
    {
        int j = id[i];
        if(dist[j] == INF) return INF;
        res += dist[j];
    }
    return res;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n,&p,&m);
    for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&id[i]);
    while( m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    int res = INF;
    for( int i = 1 ; i <= p ; i ++ ) res = min(res,spfa(i));

    printf("%d",res);

    return 0;
}
  赞
  评论
  收藏
题解 AcWing 854. Floyd求最短路
不止步于此的头像
不止步于此
2天前

题目描述

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 $k$ 个询问，每个询问包含两个整数 $x$ 和 $y$，表示查询从点 $x$ 到点 $y$ 的最短距离，如果路径不存在，则
输出 $impossible$。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

接下来 $k$ 行，每行包含两个整数 $x,y$，表示询问点 $x$ 到点 $y$ 的最短距离。

输出格式

共 $k$ 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 $impossible$。

数据范围

$1 ≤ n ≤ 200$
$1 ≤ k ≤ n^2$
$1 ≤ m ≤ 20000$
图中涉及边长绝对值均不超过 $10000$

输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

impossible
1

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 210;
int n,m,t;
int d[N][N];

int main()
{
    memset(d,0x3f,sizeof d);
    scanf("%d%d%d",&n,&m,&t);

    while( m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b] = min(d[a][b] , c);
    }

    for( int k = 1 ; k <= n ; k ++ )
        for( int i = 1 ; i <= n ; i ++ )
            for( int j = 1 ; j <= n ; j ++ )
            {
                if(i == j) d[i][j] = 0;
                else d[i][j] = min(d[i][j] , d[i][k] + d[k][j]);
            }

    while( t -- )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b] > 0x3f3f3f3f / 2) printf("impossible\n");
        else printf("%d\n",d[a][b]);
    }

    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 1128. 信使
不止步于此的头像
不止步于此
2天前 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int n,m;
int d[N][N];

int main()
{
    memset(d,0x3f,sizeof d);
    scanf("%d%d",&n,&m);

    while( m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b] = d[b][a] = min(d[a][b] , c);
    }

    for( int k = 1 ; k <= n ; k ++ )
        for( int i = 1 ; i <= n ; i ++ )
            for( int j = 1 ; j <= n ; j ++ )
            {
                if(i == j) d[i][j] = 0;
                else d[i][j] = min(d[i][j] , d[i][k] + d[k][j]);
            }

    int res = 0;
    for( int i = 1 ; i <= n ; i ++ )
    {
        if(d[1][i] == 0x3f3f3f3f)
        {
            res = -1;
            break;
        }
        else res = max(res,d[1][i]);
    }

    printf("%d",res);

    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 1129. 热浪
不止步于此的头像
不止步于此
2天前 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2510,M = 6200 * 2 + 10;
int n,m,S,T;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],q[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

void spfa()
{
    memset(dist,0x3f,sizeof dist);
    int hh = 0,tt = 1;
    q[0] = S,st[S] = true;
    dist[S] = 0;

    while( hh != tt )
    {
        int t = q[hh++];
        if(hh > N) hh = 0;
        st[t] = false;

        for( int i = h[t] ; i != -1 ; i = ne[i] )
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q[tt++] = j;
                    if(tt > N) tt = 0;
                }
            }
        }
    }
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    while( m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    spfa();
    printf("%d",dist[T]);

    return 0;
}
  赞
  评论
  收藏
题解 AcWing 852. spfa判断负环
不止步于此的头像
不止步于此
3天前

题目描述

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

输出格式

如果图中存在负权回路，则输出 $Yes$，否则输出 $No$。

数据范围

$1 ≤ n ≤ 2000$
$1 ≤ m ≤ 10000$
图中涉及边长绝对值均不超过 $10000$

输入样例：

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：

Yes

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 2010,M = 10010;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;
    for( int i = 1 ; i <= n ; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while( q.size() )
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for( int i = h[t] ; i != -1 ; 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) return true;
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);

    while( m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    if(spfa()) printf("Yes");
    else printf("No");

    return 0;
}
  赞
  评论
  收藏
题解 洛谷 P5057. [CQOI2006]简单题（树状数组）
不止步于此的头像
不止步于此
3天前

题目描述

有一个 $n$ 个元素的数组，每个元素初始均为 $0$。有 $m$ 条指令，要么让其中一段连续序列数字反转 ——
$0$ 变 $1$，$1$ 变 $0$（操作 $1$），要么询问某个元素的值（操作 $2$）。 例如当 $n = 20$ 时，$10$ 条指令如下：

QQ图片20230129003003.png

输入格式

第一行包含两个整数 $n, m$，表示数组的长度和指令的条数； 以下 $m$ 行，每行的第一个数 $t$ 表示操作的种类：

若 $t = 1$，则接下来有两个数 $L, R$，表示区间 $[L, R]$ 的每个数均反转； 若 $t = 2$，则接下来只有一个数 $i$，
表示询问的下标。

输出格式

每个操作 $2$ 输出一行（非 $0$ 即 $1$），表示每次操作 $2$ 的回答。

数据范围

$1 ≤ n ≤ 10^5$
$1 ≤ m ≤ 5 × 10^5$
保证 $L ≤ R$

输入样例

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

输出样例

1
0
0
0
1
1

思路

1. 输出只有 0 和 1 两种，可能可以用 %2 操作（管他呢，反正方法想到一个算一个）
2. 显然这是一道区间修改和单点查询的题目，我们优先考虑一下树状数组能不能解决（线段树实在麻烦），据平生所学，
   需要用树状数组维护原数组的差分数组。
3. 将 0 或 1 取反，等同于将其 + 1 再 % 2，所以将某个区间取反，等同于将该区间的每个数都 + 1 再 % 2，
   那么现在，区间修改的操作就变为了每个数 + 1，单点查询时再 % 2 即可。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int n,m;
int tr[N];

int lowbit(int x)
{
    return x & - x;
}

void add(int x,int c)
{
    for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);

    while( m -- )
    {
        int t;
        scanf("%d",&t);
        if(t == 1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            add(l,1);
            add(r+1,1);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",sum(x) % 2);
        }
    }

    return 0;
}
  赞
  评论
  收藏
题解 AcWing 851. spfa求最短路
不止步于此的头像
不止步于此
3天前

题目描述

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 $impossible$。

数据保证不存在负权回路。

输入格式

第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

输出格式

输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。

如果路径不存在，则输出 $impossible$。

数据范围

$1 ≤ n,m ≤ 10^5$
图中涉及边长绝对值均不超过 $10000$

输入样例：

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

输出样例：

2

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;

    while( q.size() )
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for( int i = h[t] ; i != -1 ; i = ne[i] )
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) printf("impossible");
    else printf("%d",dist[n]);
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for( int i = 0 ; i < m ; i ++ )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    spfa();

    return 0;
}
  赞
  评论
  收藏