最短路问题

稠密图：m与n^2相当，使用朴素Dijkstra算法

稀疏图：m与n相当，使用堆优化版Dijkstra算法或SPFA算法

朴素dijkstra算法

时间复杂度 O(n^2+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
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 (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
	}

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

Dijkstra求最短路

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

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

数据范围

1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例：
1
2
3
4
3 3
1 2 2
2 3 1
1 3 4
输出样例：
1
3
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int N  = 10;
int dis[N];
int g[N][N];
int st[N];

/*
	dijkstra的思路-》 找到到达最短边且没有被松弛过， 对这个边进行松弛 -》 依靠这个边能否削减到达其他点的距离
*/
int find(int n) {
	dis[1] = 0;
	for (int i = 0; i < n - 1; i++) {
		int t = -1;
        // 寻找一个没有被松弛过的最短点
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dis[j] < dis[t])) {
				t = j;
			}
		}
		// 将其标记松弛
		st[t] = 1;
        // 查看有没有点可以依靠他削减距离（松弛）
		for (int k = 1; k <= n; k++) {
			if (!st[k] && dis[k] > dis[t] + g[t][k]) {
				dis[k] = dis[t] + g[t][k];
			}
		}
	}
	if (dis[n] == 0x3f3f3f3f) {
		return -1;
	} else {
		return dis[n];
	}
}
int main() {
	memset(dis, 0x3f, sizeof dis);
	memset(dis, 0x3f, sizeof g);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
        // 一定要注意审题，题目中提到该边是有想的且会出现重边
		g[a][b] = min(g[a][b],c);
	}
	cout << find(n) << endl;
}
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

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 (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

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

        st[t] = true;
    }

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

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

    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

堆优化版dijkstra

时间复杂度 O(mlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
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 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] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
      	}
	}

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

Dijkstra求最短路 II

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

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

数据范围

1≤n,m≤1.5×1e5,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 1e9。

输入样例：
1
2
3
4
3 3
1 2 2
2 3 1
1 3 4
输出样例：
1
3
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
	思路： 因为考虑到断点的个数很多，我们如果遍历的化会有很大的耗时，我们本质上是寻找距离最小点可以利用大根堆来解决对于的stl是priroity 同时它默认是降序的我们需要定义一些 priority<PII,vector<PII>,great<PII>> 来进行定义让他成为小根堆，同时直接声明二维数组的方法也就会变得不适用因为点的离散行我们可以用链表的方式进行存储
*/

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int N = 200100;
int e[N],ne[N],f[N],h[N],idx = 0;
int st[N];
int dis[N];
void add(int a,int b,int c) {
	e[++idx] = b; 
	h[idx] = c;
	ne[idx] = f[a];
	f[a] = idx;
}
int dj(int n) {
	priority_queue<PII,vector<PII>,greater<PII>> que;
	dis[1] = 0;
	que.push({0,1});
	while(!que.empty()){
		auto front = que.top();
		que.pop();
		if (st[front.second]) continue;
		if (front.second == n) return front.first;
		st[front.second] = 1;
		for(int i=f[front.second];i;i = ne[i]){
			if (dis[e[i]] > dis[front.second] + h[i]) {
				dis[e[i]] = dis[front.second] + h[i];
				que.push({dis[e[i]],e[i]});
			}
		}
	}
	return -1;	
}
int main() {
	int n,m;cin>>n>>m;
	memset(dis,0x3f,sizeof dis);
	while(m--){
		int a,b,v;cin>>a>>b>>v;
		add(a,b,v);
	}
	cout<<dj(n)<<endl;
}
/*
3 3
1 2 2
2 3 1
1 3 4

*/
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

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

int dijkstra()
{
    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();

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

    printf("%d\n", dijkstra());

    return 0;
}

Bellman-Ford算法

时间复杂度 O(nm)

注意在模板题中需要对下面的模板稍作修改，加上备份数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

有边数限制的最短路

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

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

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

输入格式

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

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

点的编号为 1∼n。

输出格式

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

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

数据范围

1≤n,k≤500;

1≤m≤10000;
1≤x,y≤n
任意边长的绝对值不超过 10000。

输入样例：
1
2
3
4
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
1
3
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
	难点： 如何记录操作次数  使用一个工具数组每一次存储当前的上一个然后利用for循环避免顺序利用的问题
	难点： 如何处理负边的情况 Ford
	
*/

#include<bits/stdc++.h>
using namespace std;
const int N  = 20000;
struct edge {
	int a,b,c;
	edge(){}
	edge(int a,int b,int v):a(a),b(b),c(v){}
};
vector<edge>road;
// 这一次
int dis[N];
// 上一次
int last[N];
void add(int a, int b, int c) {
	edge e(a,b,c);
	road.push_back(e);
}
void flod(int n, int k) {
	
	memset(last,0x3f,sizeof last);
	last[1] = 0;
	for(int i=0;i<k;i++){
		memcpy(dis,last,sizeof dis);
        // dis是当前使用的个点距离 通过比较dis来计算last(最终汇报的距离)
		for(int j=0;j < road.size();j++){
			int a = road[j].a;
			int b = road[j].b;
			int c = road[j].c;
			if (dis[b] > dis[a] + c) {
				last[b] = min(last[b],dis[a] + c);
                // 可能存在多个结论取最优
			}
		}
	}
    // 因为有负边所有有的点可能被负边污染，需要减缓判断力度，同时防止-1点即使结论又是距离的q
	if (last[n] > 0x3f3f3f3f/2) {
	    cout<<"impossible"<<endl;
	} else {
	    cout<<last[n]<<endl;
	}
}

int main() {
	memset(dis,0x3f,sizeof dis);
	int n,m,k;cin>>n>>m>>k;
	while(m--){
		int a,b,v;cin>>a>>b>>v;
		add(a,b,v);
	}
	flod(n,k);
}
/*

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

*/

spfa 算法（队列优化的Bellman-Ford算法)

时间复杂度 平均情况下 O(m)，最坏情况下 O(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()){
        auto 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])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
	}

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

spfa求最短路

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

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

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

输入格式

第一行包含整数 n和 m。

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

输出格式

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

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

数据范围

1≤n,m≤1e5,
图中涉及边长绝对值均不超过 10000。

输入样例：
1
2
3
4
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
1
2
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
	spfa 相较于 ford它更加关注与变化 只会对产生变化的元素进行调整，利用一个队列和标记数组，如果因为头元素导致某个元素发生变化则会查看标记数组如果该元素不在队列中那么会加入。
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 100200;
int e[N],ne[N],v[N],f[N],idx;
int dis[N],st[N];
int m,n;
void add(int a,int b,int c) {
	for(int i=f[a];i;i = ne[i]){
		if (e[i] == b) {
			v[i] = min(v[i],c);return;
		}
	}
    // 因为题目中说明有重边的情况我们只采用最小边
	e[++idx] = b;
	ne[idx] = f[a];
	f[a] = idx;
	v[idx] = c;
}
void spfa() {
	dis[1] = 0;
	queue<int> que;
	que.push(1);
	while(!que.empty()){
	    
		int front = que.front();que.pop();
		st[front] = 0;
		for(int i=f[front];i;i = ne[i]){
			if (dis[e[i]] > dis[front] + v[i]) {
				dis[e[i]] = dis[front] + v[i];
				if (!st[e[i]]) {
					que.push(e[i]);
					st[e[i]] = 1;
				}
			}
		}
	}
	if (dis[n] >= 0x3f3f3f3f/2) {
		cout<<"impossible"<<endl;
	} else {
		cout<<dis[n]<<endl;
	}
	
}
int main() {
	cin>>n>>m;
	memset(dis,0x3f,sizeof dis);
	while(m--){
		int a,b,w;cin>>a>>b>>w;
		add(a,b,w);
	}
	spfa();
	
	
}
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

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

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

    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 = spfa();
	// 因为增加了起始位置的xian'zhi
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

spfa判断图中是否存在负环

时间复杂度是 O(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto 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;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
}

return false;

}

spfa判断负环

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

数据范围

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

输入样例：
1
2
3
4
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
1
Yes
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
	需要增加一个记录到达此位置需要的边数的数组进行记录，如果他的个数大于n就任务出现了环，同时该题目并未说明图是联通的需要分析考虑
*/

#include<bits/stdc++.h>
using namespace std;
const int N = 2100;
int e[N],ne[N],f[N],val[N];
int n,m,idx = 0;
int st[N],cnt[N],dis[N];
void add(int a,int b,int v) {
	e[++idx] = b;
	ne[idx] = f[a];
	f[a] = idx;
	val[idx] = v;
}

bool spfa(int b) {
	queue<int> qu;	
	dis[b] = 0;
	qu.push(b);
	while(!qu.empty()){
		int fr = qu.front();qu.pop();st[fr] = 0;
		for(int i=f[fr];i;i = ne[i]){
			if (dis[e[i]] > dis[fr] + val[i]) {
				dis[e[i]] = dis[fr] + val[i];
				cnt[e[i]] = cnt[fr] + 1;
                // 注意细节
				if (!st[e[i]]) {
					st[e[i]] = 1;
					qu.push(e[i]);
				}
				// 如果发现它是有环的直接输出并且返回true
				if (cnt[e[i]] > n) {
					cout<<"Yes"<<endl;
					return true;
				}
			}
		}
	}
	int i=1;
	// 如果该图不联通需要进行判断
	for(;i<=n;i++){
		if (dis[i] == 0x3f3f3f3f) {
			if (spfa(i))  break;
		}
	}
	return false;
}

int main() {
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m;
	while(m--){
		int a,b,v;cin>>a>>b>>v;
		add(a,b,v);
	}
	if (spfa(1)) {
		cout<<"No"<<endl;
	}
}

floyd算法

时间复杂度是 O(n^3)

Floyd求最短路

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

输入样例：
1
2
3
4
5
6
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
1
2
impossible
1
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
	遍历每一个元素 查看是否能通过这个元素使两点的距离变短
	诺有
	1 -》 3 -》 7 -》 9 -》 10；
	遍历到3可以收敛1-》7 
	遍历到7 可以收敛 1 - 9 3-》9
	遍历到 9 可以收敛 7 - 10，3 - 10，1 -10；
	同时 反转 + 乱序
	1-》9-》2-》7-》10；
	遍历到可以收敛 9 - 》7；
	遍历到7可以收敛 2-》10， 9-10；
	遍历到9可以收敛 1 -》2， 1-》7， 1-》10
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int dis[N][N];
void Floyd(int n) {
    //选择好塞入边 要求不能有负权回路 因为任意a->v内部都是有1-n中的点组成 如果发现有此次遍历只是收敛整个距离中的一个环节，环环相扣才能得到答案 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
                // 不要忘记边是自己到自己的情况
				if (j == k) {
					dis[j][k] = 0;
				} else if (dis[j][k] > dis[j][i] + dis[i][k]) {
					dis[j][k] = dis[j][i] + dis[i][k];
				}
			}
		}
	}
}
int main() {
	memset(dis,0x3f, sizeof dis);
	int n,m,k;
	cin>>n>>m>>k;
	while(m--){
		int a,b,v;cin>>a>>b>>v;
		dis[a][b] = min(dis[a][b], v);
	}
	Floyd(n);
	while(k--){
		int a,b;cin>>a>>b;
        // 用于处理负边的情况
		if (dis[a][b] > 0x3f3f3f3f/2) {
			cout<<"impossible"<<endl;
		} else {
			cout<<dis[a][b]<<endl;
		}
	}
	
}
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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()
{
    
    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, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}