一、【模板】单源最短路1

给你一个无向图，图中包含 5000 个点 m 个边，任意两个点之间的距离是 1 ，无重边或自环。请求出1号点到n号点的最短距离。

注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.
输入描述：
第一行两个整数n和m，表示图的点和边数。
接下来m行，每行两个整数u，v，表示u到v有一条无向边。
1≤n≤5000
1≤m≤50000
输出描述：
输出一行，表示1到n的最短路，如不存在，输出-1.

解法:

注意看题目的数据范围
不难发现这是一个稀疏图
而堆优化版dijkstra适合稀疏图
直接堆优化上就好了

#include

using namespace std;

const int maxn=1.5e5;  
int e[maxn],ne[maxn],h[maxn],dis[maxn],idx,w[maxn];
bool vis[maxn];
int n,m;
typedef pair<int ,int >PII;
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int  dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII>>mo;
    dis[1]=0;
    mo.push({0,1});
    while(mo.size())
    {
        auto t=mo.top();
        mo.pop();
        int ver=t.second,distance=t.first;
        if(vis[ver]) continue;
        vis[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>w[i]+distance)
            {
                 dis[j]=w[i]+distance;
                 mo.push({dis[j],j});
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    else return dis[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    int x,y,z,i;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
    cout<<dijkstra()<<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
54
55

二、 走迷宫

给定一个n×m的网格，在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物，放有障碍物的格子不能到达。求从(xs,ys)到(xt,yt)最少的移动次数。若不能到达，输出-1−1。
输入描述：
第一行输入两个整数n,m (1≤n,m≤1000)，表示网格大小。
第二行输入四个整数xs,ys,xt,yt
(1≤xs,xt ≤n, 1≤ys ,yt ≤m)，表示起点和终点的坐标。
接下来的n行，每行输入一个长度为m的字符串。其中，第ii行第jj个字符表示第ii行第jj列的格子上的障碍物情况，若字符为’*‘，则格子上有障碍物，若字符为’.'，则格子上没有障碍物。
保证起点不存在障碍物。
输出描述：
输出一行一个整数，表示从(xs,ys)到(xt,yt)最少的移动次数。
示例1
输入：
5 5
1 1 5 5
…
****.
…
.
…
复制
输出：
12
复制
示例2
输入：
5 5
1 1 4 5
…
****.
…
.
…
复制
输出：
-1
复制
示例3
输入：
5 5
1 1 5 5
…
****.
…

---

…
复制
输出：
-1

解法一:回溯(超时)

#include
#include
#include
#define INF 1e+7
using namespace std;
typedef struct node {
    int row;
    int col;
    node(int f, int t) :row(f), col(t) {}
}Node;
typedef struct direct {
    int crow;
    int ccol;
    direct(int f, int t) :crow(f), ccol (t) {}
}Direct;
vector<char> vec[1001];
int dp[1001][1001];
Direct dir[4] = { Direct {1,0},Direct{-1,0},Direct{0,1},Direct{0,-1} };
int main()
{
    char c;
    int xs, ys, n, m, xt, yt;
    queue<Node> qu;
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j)
            dp[i][j] = -1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c;
            if (vec[i].empty())
                vec[i].push_back('0');
            vec[i].push_back(c);
        }
    }
    qu.push(Node{ xs,ys });
    while (!qu.empty()) {
        Node point = qu.front();
        qu.pop();
        for (int i = 0; i < 4; ++i) {
            int row = point.row + dir[i].crow;
            int col = point.col + dir[i].ccol;
            if (row >= 1 && row <= n && col >= 1 && col <= m && vec[row][col] == '.' && dp[row][col] == -1) {
                qu.push(Node{ row,col });
                dp[row][col] = dp[point.row][point.col] + 1;
            }
        }
    }
    if (dp[xt][yt] != -1)
        cout << ((xt == xs && yt == ys ) ? 0 : dp[xt][yt] + 1);
    else
        cout << -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
53
54
55
56

解法二:bfs

运用BFS进行广度搜索(此方法仅用于每两个相连的点的距离都为1)；此外，如果用回溯的方***导致超时。

#include
#include
#include
#define INF 1e+7
using namespace std;
typedef struct node {
    int row;
    int col;
    node(int f, int t) :row(f), col(t) {}
}Node;
typedef struct direct {
    int crow;
    int ccol;
    direct(int f, int t) :crow(f), ccol (t) {}
}Direct;
vector<char> vec[1001];
int dp[1001][1001];
Direct dir[4] = { Direct {1,0},Direct{-1,0},Direct{0,1},Direct{0,-1} };
int main()
{
    char c;
    int xs, ys, n, m, xt, yt;
    queue<Node> qu;
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j)
            dp[i][j] = -1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c;
            if (vec[i].empty())
                vec[i].push_back('0');
            vec[i].push_back(c);
        }
    }
    qu.push(Node{ xs,ys });
    while (!qu.empty()) {
        Node point = qu.front();
        qu.pop();
        for (int i = 0; i < 4; ++i) {
            int row = point.row + dir[i].crow;
            int col = point.col + dir[i].ccol;
            if (row >= 1 && row <= n && col >= 1 && col <= m && vec[row][col] == '.' && dp[row][col] == -1) {
                qu.push(Node{ row,col });
                dp[row][col] = dp[point.row][point.col] + 1;
            }
        }
    }
    if (dp[xt][yt] != -1)
        cout << ((xt == xs && yt == ys ) ? 0 : dp[xt][yt] + 1);
    else
        cout << -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
53
54
55
56