信息学奥赛一本通 1378：最短路径(shopth)

科技前沿 • 2025-03-22 09:45 • 阅读 42

大家好，我是讯享网，很高兴认识大家。

【题目链接】

【题目考点】

1. 图论：最短路径

各求最短路径算法适用情况：

dijkstra算法：图中不存在负权边，不存在负权环
bellman/ford算法与spfa算法：图中可以有负权边，如果有负权环可以检测出来
floyd算法：图中可以有负权边，不存在负权环

2. scanf返回值

scanf的返回值是正确读取变量的个数
对于scanf("%d %d", &a, &b);
如果输入1 2，正确读入两个变量，返回2。
如果输出1 -或- 1，正确读入1个变量，返回1。
注意：如果用%d读入字母，无法正确读入，输入流中会一直有该字母的信息，需要对输入流做清空后，再进行后面的输入。

讯享网

【解题思路】

本题图中可能存在负权边，因此不能用dijkstra算法。可以使用spfa算法。
本题顶点数最大为80，可以使用复杂度为 $O(V^3)$ 的floyd算法。

输入处理：必须使用scanf来输入。如果正确输入一个数字，scanf返回1。如果遇到’-'，那么没有正确输入数字，会返回0。

【题解代码】

解法1：Spfa算法

#include <bits/stdc++.h> using namespace std; #define N 105 #define INF 0x3f3f3f3f int n, v0, edge[N][N], dis[N]; bool vis[N]; void spfa() { 
    queue<int> que; que.push(v0); vis[v0] = true; memset(dis, 0x3f, sizeof(dis)); dis[v0] = 0; while(que.empty() == false) { 
    int u = que.front(); que.pop(); vis[u] = false; for(int i = 1; i <= n; ++i) { 
    if(edge[u][i] < INF && dis[i] > dis[u] + edge[u][i]) { 
    dis[i] = dis[u] + edge[u][i]; if(vis[i] == false) { 
    vis[i] = true; que.push(i); } } } } } int main() { 
    int a; scanf("%d %d", &n, &v0); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { 
    if(scanf("%d", &a) == 1)//如果是正确输入，会返回1  edge[i][j] = a; else edge[i][j] = INF; } spfa(); for(int i = 1; i <= n; ++i) { 
    if(i != v0) printf("(%d -> %d) = %d\n", v0, i, dis[i]); } return 0; }

讯享网

解法2：Floyd算法

讯享网#include <bits/stdc++.h> using namespace std; #define N 105 #define INF 0x3f3f3f3f int n, v0, dis[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) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } int main() { 
    int a; scanf("%d %d", &n, &v0); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { 
    if(scanf("%d", &a) == 1)//如果是正确输入，会返回1  dis[i][j] = a; else dis[i][j] = INF; } floyd(); for(int i = 1; i <= n; ++i) { 
    if(i != v0) printf("(%d -> %d) = %d\n", v0, i, dis[v0][i]); } return 0; }