头像

原神高手




离线:12小时前


最近来访(32)
用户头像
安意
用户头像
青玄
用户头像
没有陷的包子
用户头像
Panson
用户头像
我永远喜欢七海
用户头像
二垚
用户头像
白金之星.
用户头像
Z-Wiskey
用户头像
kewu
用户头像
不AK不改名123
用户头像
道理都懂就不ac
用户头像
社会废人
用户头像
万星时代


原神高手
21小时前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

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

        res += dist[t];
        st[t] = true;

        for(int j = 1; j <= n; j++ ) dist[j] = min(dist[j], g[t][j]);

    }
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if(t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}


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

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

const int N = 210;

int n, m, Q;
int d[N][N];

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));

    cin >> n >> m >> Q;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j) d[i][j] = 0;
        }
    }

    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while(Q--)
    {
        int a, b;
        cin >> a >> b;
        if(d[a][b] > 0x3f3f3f3f / 2) puts("impossible");
        else cout << d[a][b] << endl;
    }

}


活动打卡代码 AcWing 852. spfa判断负环

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

const int N = 10010;

int n, m;
int e[N], ne[N], h[N], w[N], idx;
int dist[N], cnt[N]; //cnt[N] 表示1到x的最短路的边数
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()
{
    queue<int> q;
    for(int i = 1; i <= n; i++) //点1可能到不了有负环的点,因此将所有点加入队列
    {
        st[i] = true;
        q.push(i);
    }

    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; //如果超过n,根据抽屉原理,肯定经过同一个点两次,说明有环
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if(spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

spfa

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

const int N = 100010;

int n, m;
int e[N], ne[N], h[N], w[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) cout << "impossible" << endl;
    else cout << dist[n] << endl;
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();
    return 0;
}



有边数限制的负权边

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

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edge{
    int a, b, w;
}edges[M]; //用结构体保存每条边的数据

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

    for(int i = 0; i < k; i++)
    {
        memcpy(backup, dist, sizeof(dist)); //备份数据,防止串联,超过最多经过k条边的限制
        for(int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w); //使用备份数据更新最短距离
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n];
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    bellman_ford();
}



堆优化的Dijkstra算法,适用于稀疏图

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

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int e[N], ne[N], h[N], idx;
int w[N];
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++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap; //定义一个小根堆
    heap.push({0, 1}); //first为距离,second为点

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int k = t.second, distance = t.first;
        if(st[k]) continue; //如果这个点的最短路已经确定,就停止进行
        st[k] = true;

        for(int i = h[k]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i]) //更新最短距离
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    return 0;
}



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

const int N = 510;

int n, m;
int dist[N]; //记录每一个点距离第一个点的距离
int g[N][N]; //稠密阵用邻接矩阵存储
bool st[N]; //记录该点的最短距离是否已经确定

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0; 

    for(int i = 0; i < n; i++)
    {
        int t = -1; //t存储当前访问的点
        for(int j = 1; j <= n; j++) //遍历 dist 数组,找到没有确定最短路径的节点中距离源点最近的点t
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        st[t] = true;

        for(int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]); //依次更新每个点所到相邻的点最短路径值
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    memset(g, 0x3f, sizeof(g));

    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);//如果发生重边的情况则保留最短的一条边
    }
    cout << dijkstra() << endl;
    return 0;
}



活动打卡代码 AcWing 845. 八数码

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

int bfs(string start)
{
    queue<string> q;
    unordered_map<string, int> d;

    string end = "12345678x";

    q.push(start); //初始化队列和d数组
    d[start] = 0;  //d{"12345678x", 0}

    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; //转移方式

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int distance = d[t];  //定义当前状态的距离
        if(t == end) return distance; //如果是最终状态就返回距离

        int k = t.find('x');      //找到x的下标
        int x = k / 3, y = k % 3; //字符串下标 ——> 二维数组下标

        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];  //求转移后坐标
            if(a >= 0 && a < 3 && b >= 0 && b < 3) //如果没有出界
            {
                swap(t[k], t[a * 3 + b]); //二维数组下标 ——> 字符串下标,状态转移
                if(!d.count(t)) //如果这个状态没有被遍历过
                {
                    d[t] = distance + 1; //记录距离
                    q.push(t);           //将这个状态入队
                }
                swap(t[k], t[a * 3 + b]);//还原到转移之前的状态,进行下一次转移
            }
        }
    }
    return -1;
}

int main()
{
    string start;
    for(int i = 0; i < 9; i++)
    {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start) << endl;
    return 0;
}




#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N];
int r[N]; //入度

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

bool topsort()
{
    int hh = 0, tt = -1;

    for(int i = 1; i <= n; i++)
    {
        if(r[i] == 0) q[++tt] = i;//如果入度为0,就进入队列
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];  //将j的入度减为0并加入队列
            r[j]--; 
            if(r[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1; //判断是否全部元素进入队列,即存在拓扑序
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));

    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        r[b]++;   //b的入度加一
    }
    if(topsort())
    {
        for(int i = 0; i < n; i++) cout << q[i] << ' ';
    }
    else cout << -1;
}


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

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

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];

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

int bfs()
{
    int tt = 0, hh = 0;
    q[0] = 1;

    memset(d, -1, sizeof(d));
    d[1] = 0;

    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}

int main()
{
    memset(h, -1, sizeof(h));

    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}