头像

luxury




离线:20小时前



luxury
12天前
    #include<iostream>
    #include<cstring>
    using namespace std;
    const int N = 25010;
    int h[N], e[N], ne[N], w[N], idx;
    int dist[N], q[N];
    bool vis[N];
    int T, R, P, S;

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

    void spfa()
    {
        int hh = 0, tt = -1;
        memset(dist, 0x3f, sizeof dist);
        dist[S] = 0;
        vis[S] = true;
        q[++tt] = S;
        while (hh <= tt)
        {
            int t = q[hh++];
            vis[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 (!vis[j])
                    {
                        if(hh <= tt && dist[j] <= dist[q[hh]])   q[--hh] = j;
                        else    q[++tt] = j;
                        vis[j] = true;
                    }
                }
            }
        }
    }
    int main()
    {
        memset(h, -1, sizeof h);
        scanf("%d%d%d%d", &T, &R, &P, &S);
        int a, b, c;
        while(R--)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }
        while(P--)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }

        spfa();

        for(int i = 1; i <= T; i++)
        {
            if(dist[i] == 0x3f3f3f3f)    puts("NO PATH");
            else    printf("%d\n", dist[i]);
        }
        return 0;
    }



活动打卡代码 AcWing 854. Floyd求最短路

luxury
12天前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
int d[N][N];
int n, m, q;
void floyd()
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}
int main()
{
    memset(d, 0x3f, sizeof d);
    scanf("%d%d%d", &n, &m, &q); 
    for(int i = 1; i <= n; i++)     d[i][i] = 0;
    int a, b, c;
    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    floyd();
    while(q--)
    {
        scanf("%d%d", &a, &b);
        if(d[a][b] > 0x3f3f3f3f / 2)    puts("impossible");
        else    printf("%d\n", d[a][b]);
    }
    return 0;
}


活动打卡代码 AcWing 839. 模拟堆

luxury
15天前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int h[N], ph[N], hp[N], maxsize;

/*
ph[k]:第k个插入的数在堆中的下标
与ph[k]为映射关系
*/

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}


void down(int u)
{
    int t = u;
    if(2 * u <= maxsize && h[2 * u] < h[t])    t = 2 * u;
    if(2 * u + 1 <= maxsize && h[2 * u + 1] < h[t])    t = 2 * u + 1;
    if(u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}


int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while(n--)
    {
        char op[5];
        int x, k;
        scanf("%s", op);
        if(*op == 'I')
        {
            scanf("%d", &x);
            h[++maxsize] = x;
            m++;
            ph[m] = maxsize;
            hp[maxsize] = m;
            up(maxsize);
        } 
        else if(!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, maxsize);
            maxsize--;
            down(k), up(k);
        }
        else if(op[0] == 'C')
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
        else if(op[0] == 'P')
        {
            printf("%d\n", h[1]);
        }
        else
        {
            heap_swap(1, maxsize);
            maxsize--;
            down(1);
        }
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 838. 堆排序

luxury
15天前
#include<iostream>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], maxSize;

void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

void down(int u)
{
    int t = u;
    if(2 * u <= maxSize && h[2 * u] < h[t])    t = 2 * u;
    if(2 * u + 1 <= maxSize && h[2 * u + 1] < h[t])    t = 2 * u + 1;
    if(u != t)
    {
        swap(h[t], h[u]);
        down(t);        
    }

}

int main()
{
    scanf("%d%d", &n, &m);
    maxSize = n;
    for(int i = 1; i <= n; i++)     scanf("%d", &h[i]);
    for(int i = n / 2; i > 0; i--)      down(i);
    while(m--)
    {
        printf("%d ", h[1]);
        h[1] = h[maxSize--];
        down(1);
    }
    return 0;
}


活动打卡代码 AcWing 844. 走迷宫

luxury
16天前
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], dist[N][N];
int n, m;
int bfs()
{
    memset(dist, -1, sizeof dist);
    dist[0][0] = 0;
   int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    //int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    queue<PII> q;
    q.push({0, 0});
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1 && g[x][y] == 0)
            {
                dist[x][y] = dist[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return dist[n-1][m-1];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m ;j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
    printf("%d\n", bfs());
    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

luxury
16天前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int h[N], e[N], ne[N], idx;
int n, m;
int q[N];
int dist[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs()
{
    int hh = 0, tt = -1;
    memset(dist, -1, sizeof dist);
    dist[1] = 0;
    q[++tt] = 1;
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] == -1)
            {
                dist[j] = dist[t] + 1; 
                q[++tt] = j;
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    int a, b;
    while (m--)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    bfs();
    printf("%d\n", dist[n]);
    return 0;
}



luxury
17天前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int h[N], e[N], ne[N], d[N], idx;
int n, m;
int q[N], hh = 0, tt = -1;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool toposort()
{
    for(int i = 1; i <= n; i++)     //度为零的点入队
    {
        if(!d[i])   q[++tt] = i;
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)     q[++tt] = j;
        }
    }
    return tt == n - 1;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    int a, b;
    while(m--)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b]++;
    }
    if(!toposort())     puts("-1");
    else
    {
        for(int i = 0; i < n; i++)      printf("%d ", q[i]);
        printf("\n");
    }
    return 0;
}



luxury
17天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool vis[N];
int n, m;

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    dist[1] = 0;
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if(vis[ver])    continue;
        vis[ver] = true;
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    return (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    int a, b, c;
    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int ans = dijkstra();
    printf("%d\n", ans);
    return 0;
}



luxury
17天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int g[N][N], dist[N];
bool vis[N];
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && (t == -1 || dist[t] > dist[j]))   t = j;
        }
        if(t == n)      break;
        for(int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
        vis[t] = true;
    }
    return (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    int a, b, c;
    while(m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    int ans = dijkstra();
    printf("%d\n", ans);
    return 0;
}



活动打卡代码 AcWing 842. 排列数字

luxury
27天前
#include<iostream>
using namespace std;
const int N = 10;
int path[N];
bool st[N]; 
int n;
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++)  printf("%d ", path[i]);
        printf("\n");
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}
int main()
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}