头像

cloudinwind

郑州大学




离线:3天前


最近来访(20)
用户头像
iforget
用户头像
ぬりがよい
用户头像
includeno
用户头像
Tingting
用户头像
lxxxl
用户头像
zombotany
用户头像
小乐959
用户头像
PDX
用户头像
狐闹
用户头像
ganyiming
用户头像
纪年
用户头像
别来烦我
用户头像
zerQ
用户头像
蜗牛往上爬
用户头像
青门
用户头像
D.devil
用户头像
无名氏DU


题目描述

给定一个 $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

算法

Floyd算法

时间复杂度

$O(n^3)$

参考文献

C++ 代码

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

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;

// 稠密图用邻接矩阵存储
int d[N][N];

void floyd()
{
    // 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()
{
    scanf("%d%d%d", &n, &m, &Q);
    // 初始化
    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] = INF;
    while(m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = min(d[a][b], w);
    }

    floyd();
    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (d[a][b] > INF/2) puts("impossible");
        else printf("%d\n", d[a][b]);
    }

    return 0;
}


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

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

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;

// 稠密图用邻接矩阵存储
int d[N][N];

void floyd()
{
    // 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()
{
    scanf("%d%d%d", &n, &m, &Q);
    // 初始化
    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] = INF;
    while(m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = min(d[a][b], w);
    }

    floyd();
    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (d[a][b] > INF/2) puts("impossible");
        else printf("%d\n", d[a][b]);
    }

    return 0;
}



题目描述

给定一个 $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

算法

SPFA

时间复杂度

一般情况下是$O(m)$, 最坏情况下是$O(nm)$

参考文献

SPFA判负环.png

C++ 代码

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

using namespace std;

const int N = 100010;

int n, m;

// 稀疏图使用邻接表存储
int h[N], e[N], ne[N], w[N], idx;

// dist存储到该点的最短路径
 // cnt存储到该点的最短路径的边的数量
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 ++;
}

int spfa()
{
    queue<int> q;
    // 因为1号点(起始点)可能到不了存在负环的点
    // 因此将所有点放入队列中
    for (int i=1; i<=n; i++)
    {
        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;
                // 如果到j点的最短路径的边数大于等于n, 说明至少经过了n+1个结点, 但是一共只有n个结点, 所以一定有负环
                if (cnt[j] >= n) return true;

                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

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

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

    if (spfa()) puts("Yes");
    else puts("No");
    return 0;

}



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

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

using namespace std;

const int N = 100010;

int n, m;

// 稀疏图使用邻接表存储
int h[N], e[N], ne[N], w[N], idx;

// dist存储到该点的最短路径
 // cnt存储到该点的最短路径的边的数量
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 ++;
}

int spfa()
{
    queue<int> q;
    // 因为1号点(起始点)可能到不了存在负环的点
    // 因此将所有点放入队列中
    for (int i=1; i<=n; i++)
    {
        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;
                // 如果到j点的最短路径的边数大于等于n, 说明至少经过了n+1个结点, 但是一共只有n个结点, 所以一定有负环
                if (cnt[j] >= n) return true;

                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

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

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

    if (spfa()) puts("Yes");
    else puts("No");
    return 0;

}



题目描述

给定一个 $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

算法

SPFA

时间复杂度

一般情况下是$O(m)$, 最坏情况下是$O(nm)$

参考文献

SPFA算法原理.png

C++ 代码

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

using namespace std;

const int N = 100010;

int n, m;

// 稀疏图, 用邻接表进行存储
int h[N], e[N], ne[N], w[N], idx;

int dist[N];

bool st[N];

typedef pair<int, int> PII;

// 添加一条 从a到b 权重为c 的边
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool 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) return false;
    else return true;

}

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

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

    if (!spfa()) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}



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

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

using namespace std;

const int N = 100010;

int n, m;

// 稀疏图, 用邻接表进行存储
int h[N], e[N], ne[N], w[N], idx;

int dist[N];

bool st[N];

typedef pair<int, int> PII;

// 添加一条 从a到b 权重为c 的边
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool 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) return false;
    else return true;

}

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

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

    if (!spfa()) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}




题目描述

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

请你求出从 $1$ 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,输出 impossible

注意:图中可能 存在负权回路 。

输入格式

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

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

输出格式

输出一个整数,表示从 $1$ 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离。

如果不存在满足条件的路径,则输出 impossible

数据范围

$1≤n,k≤500,$
$1≤m≤10000,$
任意边长的绝对值不超过 $10000$。

样例

输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3

算法

Bellman-Ford

时间复杂度

$O(nm)$

参考文献

Bellman-Ford算法核心思想:

Bellman-Ford算法.png

备份原因:

备份的原因.png

C++ 代码

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

using namespace std;

const int N = 510, M = 10010;

int n, m, k;

int dist[N];    // 从起点到该点的最短距离

int backup[N];  // 备份数组

struct Edge{
    int a, b, w;
}edges[M];

bool bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    // Bellman-Ford算法核心
    for (int i=0; i < k; i++)
    {
        // 将dist备份, 每次使用上一次的迭代结果
        memcpy(backup, dist, sizeof dist);

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

    // 如果 k = 1 并且只有一条边从 结点1 到结点2, 权重为-1, 则dist[n] = -1, 因此不能返回-1作为判断条件
    if (dist[n] > 0x3f3f3f3f/2) return false;
    else return true;
}

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

    // 初始化
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    if (!bellman_ford()) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}



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

using namespace std;

const int N = 510, M = 10010;

int n, m, k;

int dist[N];    // 从起点到该点的最短距离

int backup[N];  // 备份数组

struct Edge{
    int a, b, w;
}edges[M];

bool bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    // Bellman-Ford算法核心
    for (int i=0; i < k; i++)
    {
        // 将dist备份, 每次使用上一次的迭代结果
        memcpy(backup, dist, sizeof dist);

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

    // 如果 k = 1 并且只有一条边从 结点1 到结点2, 权重为-1, 则dist[n] = -1, 因此不能返回-1作为判断条件
    if (dist[n] > 0x3f3f3f3f/2) return false;
    else return true;
}

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

    // 初始化
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    if (!bellman_ford()) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}



题目描述

给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

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

输入格式

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

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

输出格式

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

如果路径不存在,则输出 $−1$。

数据范围

$1≤n,m≤1.5×10^5,$
图中涉及边长均不小于 $0$,且不超过 $10000$。

样例

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

算法1

堆优化Dijkstra算法

时间复杂度

$O(mlogn)$

参考文献

C++ 代码

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

using namespace std;

const int N = 1e6 + 10;

int n, m;

// 稀疏图, 使用邻接表存储
int h[N], e[N], ne[N], w[N], idx;

// dist存储从起点到该点的最短路径长度
int dist[N];

// st标记结点是否已经被遍历(当前已经确定最短距离的点)
bool st[N];

typedef pair<int, int> PII;

// 添加一条 从a到b 权重为c 的边
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

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

    // 使用优先队列实现堆, 小根堆
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

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

        // ver表示图中的结点, distance表示起点到该点的距离
        int ver = t.second, distance = t.first;
        // 如果该点已被遍历
        if(st[ver]) continue;

        st[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});
            }
        }

    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

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

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

    int t = dijstra();
    printf("%d", t);
    return 0;
}



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

using namespace std;

const int N = 1e6 + 10;

int n, m;

// 稀疏图, 使用邻接表存储
int h[N], e[N], ne[N], w[N], idx;

// dist存储从起点到该点的最短路径长度
int dist[N];

// st标记结点是否已经被遍历(当前已经确定最短距离的点)
bool st[N];

typedef pair<int, int> PII;

// 添加一条 从a到b 权重为c 的边
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

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

    // 使用优先队列实现堆, 小根堆
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

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

        // ver表示图中的结点, distance表示起点到该点的距离
        int ver = t.second, distance = t.first;
        // 如果该点已被遍历
        if(st[ver]) continue;

        st[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});
            }
        }

    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

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

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

    int t = dijstra();
    printf("%d", t);
    return 0;
}