AcWing 4224. 起火迷宫

题目链接

4224. 起火迷宫 - AcWing题库

题解思路

BFS:

  1. 每次火先向四周蔓延
  2. J检查周围是否可以行走,火走过的地方就不可以继续行走了
  3. 相当于是将两个队列并行遍历检查

BFS

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
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int N = 1010;
int n, m;
char g[N][N];
int st[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};

void f(){
    cin >> n >> m;
    memset(st, -1, sizeof st);
    queue<pii> J, F;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> g[i][j];
            if(g[i][j] == 'F')F.push({i, j}),st[i][j] = 0;
            if(g[i][j] == 'J')J.push({i, j}),st[i][j] = 0;
        }
    }
    
    while(J.size()){
        int l = F.size();
        //cout << "F" << endl;
        while(l--){		//火向四周蔓延
            auto [x, y] = F.front();
            //cout << x << " " << y << endl;
            F.pop();
            for(int i = 0; i < 4; i++){
                int nx = dx[i] + x, ny = dy[i] + y;
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == '.' && st[nx][ny] == -1){
                    st[nx][ny] = st[x][y] + 1;
                    F.push({nx, ny});
                }
            }
        }
        l = J.size();
       // cout << endl << endl;
        //cout << "J" << endl;
        while(l--){		//J检查周围是否可以走
            auto [x, y] = J.front();
            //cout << x << " " << y << endl;
            J.pop();
            for(int i = 0; i < 4; i++){
                int nx = dx[i] + x, ny = dy[i] + y;
                if(!(nx >= 0 && nx < n && ny >= 0 && ny < m)){cout << st[x][y] + 1 << endl; return;}
                if(g[nx][ny] == '.' && st[nx][ny] == -1){
                    st[nx][ny] = st[x][y] + 1;
                    J.push({nx, ny});
                }
            }
        }
        //cout <<endl;
    }
    cout << "IMPOSSIBLE" << endl;
    return;
    
}

int main ()
{
    int T;
    cin >> T;
    while(T--){
        f();
    }
    return 0;
}

AcWing 4225. 石油储备

题目链接

4225. 石油储备 - AcWing题库

题解思路

用一个数组存储所有@,并且遍历这数组，BFS往八个方向行走

BFS

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 <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
int n, m, z, cnt;
const int N = 110;
int st[N][N];
char g[N][N];
vector<pii> v;

void bfs(){
    int c = 0;
    for(int i = 0; i < z; i++){
        queue<pii> q;
        auto [a, b] = v[i];
        if(st[a][b] != -1)continue;
        else st[a][b] = c++;
        q.push({a, b});
        while(q.size()){
            auto[x, y] = q.front();
            q.pop();
            for(int i = 0; i < 8; i++){
                int nx = x + dx[i], ny = y + dy[i];
                if(nx < n && nx >= 0 && ny < m && ny >= 0 && g[nx][ny] == '@' && st[nx][ny] == -1){
                    st[nx][ny] = st[x][y];
                    q.push({nx, ny});   
                }
            }      
        }
    }
    cout << c << endl;
}

int main ()
{
    while(cin >> n >> m, n != 0){
        memset(st, -1, sizeof st);
        v.clear();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> g[i][j];
                if(g[i][j] == '@')v.push_back({i, j});
            }
        }
        z = v.size();
        cnt = 0;
        bfs();
       // cout << cnt << endl;
    }
    return 0;
}

AcWing 4226. 非常可乐

题目链接

4226. 非常可乐 - AcWing题库

题解思路

相当于相互倒水，找打最小次数使得两个杯子水一样。BFS为正解

BFS

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
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define pii pair<int, int>
const int N = 110;
using namespace std;
struct Node{
    int a, b, c;    
};
int s, n, m;
int st[N][N];

//a->b
inline Node f1(Node t){
    int y = n - t.b;
    if(t.a <= y){t.b += t.a; t.a = 0;}
    else {t.a -= y; t.b = n;}
    return t;
}
//a->c
inline Node f2(Node t){
    int y = m - t.c;
    if(t.a <= y){t.c += t.a; t.a = 0;}
    else {t.a -= y; t.c = m;}
    return t;
}
//b->a
inline Node f3(Node t){
    int y = s - t.a;
    if(t.b <= y){t.a += t.b; t.b = 0;}
    else {t.b -= y; t.a = s;};
    return t;
}
//b->c
inline Node f4(Node t){
    int y = m - t.c;
    if(t.b <= y){t.c += t.b; t.b = 0;}
    else {t.b -= y; t.c = m;};
    return t;
}
//c->a
inline Node f5(Node t){
    int y = s - t.a;
    if(t.c <= y){t.a += t.c; t.c = 0;}
    else {t.c -= y; t.a = s;}
    return t;
}
//c->b
inline Node f6(Node t){
    int y = n - t.b;
    if(t.c <= y){t.b += t.c; t.c = 0;}
    else {t.c -= y; t.b = n;}
    return t;
}


void f(){
    memset(st, -1, sizeof st);
    queue<Node> q;
    q.push({s, 0, 0});
    st[s][0] = 0;
    while(q.size()){
        auto g = q.front();
        q.pop();
        if(g.a == s / 2 && g.b == s / 2){cout << st[s/2][s/2] << endl; return;}
        Node t = f1(g);
        if(st[t.a][t.b] == -1){st[t.a][t.b] = st[g.a][g.b] + 1; q.push(t);}
        t = f2(g);
        if(st[t.a][t.b] == -1){st[t.a][t.b] = st[g.a][g.b] + 1; q.push(t);}
        t = f3(g);
        if(st[t.a][t.b] == -1){st[t.a][t.b] = st[g.a][g.b] + 1; q.push(t);}
        t = f4(g);
        if(st[t.a][t.b] == -1){st[t.a][t.b] = st[g.a][g.b] + 1; q.push(t);}
        t = f5(g);
        if(st[t.a][t.b] == -1){st[t.a][t.b] = st[g.a][g.b] + 1; q.push(t);}
        t = f6(g);
        if(st[t.a][t.b] == -1){st[t.a][t.b] = st[g.a][g.b] + 1; q.push(t);}
    }
    cout << "NO" << endl;
    return;
}

int main ()
{
    while(cin >> s >> n >> m, s != 0){
        if(n < m)swap(n,  m);
        if(s % 2){cout << "NO" << endl; continue;}
        f();
    }
}

优化版

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
#include<bits/stdc++.h>
using namespace std;

using tiii = tuple<int, int, int>;
using viii = vector<int>;

int main(){
    vector<int> s(3);
    auto pull = [&](int i, int j, viii t3) -> viii{ //将 i 倒入 j 中
        int w = min(t3[i], s[j] - t3[j]);
        t3[i] -= w, t3[j] += w;
        return t3;
    };

    while(cin >> s[0] >> s[1] >> s[2] and s[0]){
        if(s[1] < s[2]) swap(s[1], s[2]);//一定是s[1] >= s[2], 这样当s[0] = s[1] && s[2] == 0时就是合法解
        bitset<101> v[101][101];//记录是否来过，无需记录值（分步bfs第几步，就是几）

        queue<viii> sk, wbw;
        queue<viii> &q = sk, &q2 = wbw;
        q.push({s[0], 0, 0});
        for(int ans = 1; q.size();ans++){//分步bfs
            for(; q.size(); q.pop()){
                auto pos = q.front();
                for(int i = 0; i < 9; i++)
                    if(i / 3 != i % 3){
                        auto np = pull(i / 3, i % 3, pos);
                        if(!v[np[0]][np[1]][np[2]]) q2.push(np), v[np[0]][np[1]][np[2]] = 1;
                    }
            }
            swap(q, q2);//交换指针
            if(v[s[0] / 2][s[0] / 2][0]) {cout << ans << endl; break;}
        }
        if(!v[s[0] / 2][s[0] / 2][0]) cout << "NO\n";
    }

    return 0;
}

AcWing 4227. 找路

题目链接

4227. 找路 - AcWing题库

题解思路

BFS模板题

BFS

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
#include<bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int N = 210;
char g[N][N];
int v1[N][N], v2[N][N];
int n, m;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};

void f(){
    memset(v1, -1, sizeof v1);
    memset(v2, -1, sizeof v2);
    queue<pii> q1, q2;
    vector<pii> u;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> g[i][j];
            if(g[i][j] == 'Y')q1.push({i, j}), v1[i][j] = 0;
            if(g[i][j] == 'M')q2.push({i, j}), v2[i][j] = 0;
            if(g[i][j] == '@')u.push_back({i, j});
        }
    }
    while(q1.size()){
        auto [x, y] = q1.front();
        q1.pop();
        for(int i = 0; i < 4; i++){
            int nx = dx[i] + x, ny = dy[i] + y;
            if(nx < n && nx >= 0 && ny < m && ny >= 0 && g[nx][ny] != '#' && v1[nx][ny] == -1){
                q1.push({nx, ny});
                v1[nx][ny] = v1[x][y] + 1; 
            }
        }
    }
    while(q2.size()){
        auto [x, y] = q2.front();
        q2.pop();
        for(int i = 0; i < 4; i++){
            int nx = dx[i] + x, ny = dy[i] + y;
            if(nx < n && nx >= 0 && ny < m && ny >= 0 && g[nx][ny] != '#' && v2[nx][ny] == -1){
                q2.push({nx, ny});
                v2[nx][ny] = v2[x][y] + 1; 
            }
        }
    }
    int res = INT_MAX;
    for(int  i = 0; i < u.size(); i++){
        auto [x, y] = u[i];
        if(v1[x][y] != -1 && v2[x][y] != -1){
            res = min(res, v1[x][y] + v2[x][y]);
        }
    }
    cout << res * 11  << endl;
    return;
}

int main ()
{
    while(cin >> n >> m){
        f();
    }
    return 0;
}

AcWing 4241. 货物运输

题目链接

AcWing 4241. 货物运输

题解思路

  • 相当于dijkstra算法，但是求解的是结点的每条路径中最大最小权重中的最大值。
  • 转移方程dist[j]=max(dist[j],min(dist[ver],k))
  • 这里的j表示下一个点，ver表示当前的点，k表示这条边的长度，只要当前的dist[j]是小于这个值的那么我们就更新dist[j]的值,这样就能让dist[j]最小路径最大值。

dijkstra优化

优先队列来松弛，每次都是如果有更新才会入队

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
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int N = 1010;
vector<vector<pii>> g;
int n, m;
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, -0x3f, sizeof dist); 
    memset(st, false, sizeof st);
    dist[1] = 0x3f3f3f3f;
    priority_queue<pii> pq; 
    pq.push({0, 1}); 

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

        int ver = t.second, w = t.first;

        if (st[ver]) continue;  
        st[ver] = true; 

        for (int i = 0; i < g[ver].size(); i++) {
            int j = g[ver][i].first;
            int k = g[ver][i].second; //到下一个节点的承重
            if (dist[j] < min(dist[ver], k)) { //当前j这个点需要求所有路径中最小值中的最大值就可以
                dist[j] = min(dist[ver], k);
                pq.push({dist[j], j});    
            }
        }
    }
    return dist[n];
}

int main()
{
    int T, a, b, c;
    cin >> T;
    for(int _ = 1; _ <= T; _++){
        cin  >> n >> m;
        
        g = vector<vector<pii>> (n + 1);
        for(int i = 0; i <= n; i++) g[i].clear();
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back({b, c});
            g[b].push_back({a, c});
        }
        cout << "Scenario #" << _ << ":" << endl;
        cout << dijkstra() << endl << endl; 
    }
    return 0;
}

一个更简单的写法是

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int edge[1010][1010], d[1010];

int main(){
    int tt; cin >> tt;
    for(int _ = 1; _ <= tt; _++){
        int n, m; cin >> n >> m;
        memset(edge, 0, sizeof edge);
        memset(d, 0, sizeof d);
        for(int a, b, c; m--;) 
            if(cin >> a >> b >> c) edge[a][b] = edge[b][a] = c;

        priority_queue<pii> pq;
        pq.push({2e9, 1}); d[0] = 2e9;
        while(pq.size()){
            auto [cd, cx] = pq.top(); pq.pop();
            if(cd < d[cx]) continue;//没有就TLE
            for(int i = 1; i <= n; i++)
                if(min(cd, edge[cx][i]) > d[i]){
                    d[i] = min(cd, edge[cx][i]);
                    pq.push({d[i], i});
                }
        }
        printf("Scenario #%d:\n%d\n\n", _ , d[n]);
    }

    return 0;
}

Acwing 4242. 货币兑换

题目链接

4242. 货币兑换 - AcWing题库

题解思路

  • 直接用spfa算法
  • spfa算法适用于无负权回路的图
  • 状态转移dist[j] = (dist[t] - c[i]) * r[i]：当前这个节点 t ——> j 用t去更新j

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
#include <bits/stdc++.h>

using namespace std;
const int N = 1010, M = 1010;
int h[N], ne[M], e[N], idx, n, m, s;
double R[M], C[M], dist[N], v;
bool st[N]; //标记的是否在队列中

void add(int a, int b, double r, double c){
    e[idx] = b, R[idx] = r, C[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa(){
    queue<int> q;
    q.push(s);
    dist[s] = v;
    st[s] = true; //在队列中
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];   //下一个元素
            if(dist[j] < (dist[t] - C[i]) * R[i]){  //查看是否大于之前节点的值
                if(j == s)return true;              //如果回到最初的节点就直接返回，说明钱一定增多
                dist[j] = (dist[t] - C[i]) * R[i];  //更新这个节点
                if(!st[j])q.push(j), st[j] = 1;     //如果队列中没有就直接入队
            }
        }
    }
    return false;
}

int main ()
{
    cin >> n >> m >> s >> v;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++){
        int a, b;
        double r1, c1, r2, c2;
        cin >> a >> b >> r1 >> c1 >> r2 >> c2;
        add(a, b, r1, c1);
        add(b, a, r2, c2);
    }
    if(spfa())cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

AcWing 4243. 传递信息

题目链接

4243. 传递信息 - AcWing题库

题解思路

求单元最短路问题，可用dijkstra算法，也可以用优化版dijkstra算法,朴素版时间复杂度是$O(n^2)$,堆优化版时间复杂度是$O(m*logn)$

dijkstra算法（朴素版）

时间复杂度$O(n^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
#include <bits/stdc++.h>

const int N = 110;
using namespace std;
int n;
int g[N][N], dist[N];
bool st[N];

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
	dist[1] = 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;                                      //记录
		}
		st[t] = true;								        //确定最小的距离，标记
		for (int j = 1; j <= n; j++) {		                //遍历每一个节点，用最小距离更新其它节点
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}

	}
}

int main ()
{
    cin >> n;
    memset(g, 0x3f, sizeof g);
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= i; j++){
            string s;
            cin >> s;
            if(s[0] != 'x'){
                int t = 0;
                for(int i = 0; i < s.size(); i++){
                    t = t * 10 + (s[i] - '0'); 
                }
                g[i + 1][j] = g[j][i + 1] = t;
            }
        }
    }
    dijkstra();
    int res = 0;
    for(int i = 2; i <= n; i++)res = max(res, dist[i]); 
    cout << res << endl;
    return 0;
}

AcWing 4244. 牛的比赛

题目链接

4244. 牛的比赛 - AcWing题库

题解思路

Floyd模板题

Floyd

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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;

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

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d",&x,&y);
        d[x][y] = d2[y][x] = 1;
        //d[x][y] = 1，代表x > y
        //d[y][x] = 1，代表y < x
    }
    //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] |= (d[i][k] && d[k][j]);//d与d2互不干扰，分开dp
                d2[i][j] |= (d2[i][k] && d2[k][j]);
            }
    //输出
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int t = 0;
        for(int j = 1; j <= n; j++)
            if(d[i][j] | d2[i][j]) t++;//可以比较i，j之间的关系
        if(t == n - 1) ans++;//可以比较其他n-1个点的关系，说明可以被定位
    }
    cout << ans;
    return 0;
}

AcWing 4246. 最短路径和

题目链接

4246. 最短路径和 - AcWing题库

题解思路

dijkstra算法

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
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int N = 1000010, M = 2000010;
int n, m;
int h1[N], h2[N], ne[M], e[M], w[M], idx;
int d1[N], d2[N];
bool st[N];

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

void dijkstra(int *h, int *d){
    memset(st, false, sizeof st);

    priority_queue<pii,vector<pii> ,greater<pii>> pq;
    pq.push({0, 1});
    d[1] = 0;
    while(pq.size()){
        auto [x, y] = pq.top();
        pq.pop();
        if(st[y] == 1)continue;
        st[y] = 1;
        for (int i = h[y]; i != -1; i = ne[i])
        {
            int j = e[i];  
            if (d[j] > d[y] + w[i]) //如果下一个元素原来距离比较大就更新距离
            {
                d[j] = d[y] + w[i];
                pq.push({d[j], j});    //插入到小根堆
            }
        }
        
    }
}

int main (){
    int T;
    cin >> T;
    while(T--){
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(d1, 0x3f, sizeof d1);
        memset(h2, -1, sizeof h2);
        memset(d2, 0x3f, sizeof d2);
        for(int i = 0; i < m; i++){
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c, h1);
            add(b, a, c, h2);
        }
        dijkstra(h1, d1);
        dijkstra(h2, d2);
        long long res = 0;
        for(int i = 1; i <= n; i++ ) res += d1[i] + d2[i];
        cout << res << endl;
    }
    return 0;
}

AcWing 4247. 糖果

题目链接

4247. 糖果 - AcWing题库

题解思路

dijkstra算法（堆优化版）

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
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int N = 30010, M = 150010;
int h[N], ne[M], e[M], w[M], idx, d[N], n, m;
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(){
    priority_queue<pii, vector<pii> ,greater<pii>> pq;
    pq.push({0, 1});
    d[1] = 0;
    while(pq.size()){
        auto [x, y] = pq.top();
        pq.pop();
        if(st[y])continue;
        st[y] = 1;
        for(int i = h[y]; ~i; i = ne[i]){
            int j = e[i];
            if(d[j] > d[y] + w[i]){		//到达j节点的距离大于（到达y节点的距离+y->j），更新j节点距离
                d[j] = d[y] + w[i];
                pq.push({d[j], j});
            }
        }
    }
}

int main ()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);
    for(int i = 0; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    dijkstra();
    cout << d[n] << endl;
    return 0;
}

AcWing 4248. 地铁

题目链接

4248. 地铁 - AcWing题库

题解思路

两种方法:

  1. 是Floyd算法（此题数据比较小可以用）.
  2. dijkstra算法

Floyd算法

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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 210, M = 40010;
double g[N][N];
bool st[N];
vector<pii> p, p1;	//p是总数组，p1是暂存数组
map<pii, int> mp;
int n, a, b;

//求两个地铁站步行的时间
inline double d(pii a, pii b){
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy) * 0.006; // 相当于距离除速度，10km/h = 10000m/60min
}

int main ()
{
    //初始化
    for(int i = 0; i < N; i++) 
        for(int j = 0; j < N; j++) 
           if(i != j) g[i][j] = 2e18;
           else g[i][j] = 0;	
    
    ll x, y, x1, y1, k = 0;
    cin >> x >> y >> x1 >> y1;
    p.push_back({x, y}); p.push_back({x1, y1});	//两个点加入到数组中去
    mp[{x, y}] = k++; mp[{x1, y1}] = k++;		//用map保存下来，以后如果遇到之后就不用再加入到数组中去
    while(cin >> x >> y){
        if(x == -1 && y == -1){
            for(int i = 0; i < p1.size(); i++){
                int t1 = mp[p1[i]];
                //cout << p1[i].first<< " " << p1[i].second << " " << t1 << endl;
                for(int j = i + 1; j < p1.size(); j++){
                    int t2 = mp[p1[j]];
                    //cout << t2 << endl;
                    int t3 = mp[p1[j - 1]];
                    g[t1][t2] = g[t2][t1] = g[t1][t3] + d(p1[j], p1[j - 1]) / 4;	//由于直接算距离过大，会导致溢出，所以利用前一个站点来计算
                    //cout << g[t1][t2] << endl;
                }
            }
            p1.clear();
            //cout <<endl;
        }else{
            p1.push_back({x, y});
            if(!mp.count({x, y})){	//如果之前的节点没有出现过就直接加入到总数组中去
                mp[{x,y}] = k++;
                p.push_back({x, y});                
            }
        }
    }
    n = p.size();//总的节点个数
    
    //因为到有些走过去站点可能会更快
    for(int i = 0; i < n; i++){
        //cout << p[i].first<< " " << p[i].second << endl;
        for(int j = 0; j < n; j++){
            g[i][j] = min(g[i][j], d(p[i], p[j]));  //行走
        }
        //cout << endl;
    }
    
    //Floyd算法（可以求出任何两点之间的最短时间）
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    cout << (int)(g[0][1] + 0.5) << endl;
    return 0;
}

Dijkstra算法

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
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 210, M = 40010;
double dist[N];
bool st[N];
double g[N][N];
vector<pii> p, p1;
map<pii, int> mp;
int n, a, b;

//求两个地铁站步行的时间
inline double d(pii a, pii b){
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy) * 0.006; // 相当于距离除速度，10km/h = 10000m/60min
}

void dijkstra(){
    for(int i = 0; i < n; i++)dist[i] = 2e18;
	dist[0] = 0;
	for (int i = 0; i < n; i++) {
		int t = -1;        									//标记是否被用过
		for (int j = 0; j < n; j++) {				//记录下没有被确定路径的最短距离的那个
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		}
		st[t] = true;								//将当前路径确定
		for (int j = 0; j < n; j++) {				//更新最短路径
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
}

int main ()
{
    //初始化
    for(int i = 0; i < N; i++) 
        for(int j = 0; j < N; j++) 
           if(i != j) g[i][j] = 2e18;
           else g[i][j] = 0;	
    
    ll x, y, x1, y1, k = 0;
    cin >> x >> y >> x1 >> y1;
    p.push_back({x, y}); p.push_back({x1, y1});	//两个点加入到数组中去
    mp[{x, y}] = k++; mp[{x1, y1}] = k++;		//用map保存下来，以后如果遇到之后就不用再加入到数组中去
    while(cin >> x >> y){
        if(x == -1 && y == -1){
            for(int i = 0; i < p1.size(); i++){
                int t1 = mp[p1[i]];
                //cout << p1[i].first<< " " << p1[i].second << " " << t1 << endl;
                for(int j = i + 1; j < p1.size(); j++){
                    int t2 = mp[p1[j]];
                    //cout << t2 << endl;
                    int t3 = mp[p1[j - 1]];
                    g[t1][t2] = g[t2][t1] = g[t1][t3] + d(p1[j], p1[j - 1]) / 4;	//由于直接算距离过大，会导致溢出，所以利用前一个站点来计算
                    //cout << g[t1][t2] << endl;
                }
            }
            p1.clear();
            //cout <<endl;
        }else{
            p1.push_back({x, y});
            if(!mp.count({x, y})){	//如果之前的节点没有出现过就直接加入到总数组中去
                mp[{x,y}] = k++;
                p.push_back({x, y});                
            }
        }
    }
    n = p.size();//总的节点个数
    
    //因为到有些走过去站点可能会更快
    for(int i = 0; i < n; i++){
        //cout << p[i].first<< " " << p[i].second << endl;
        for(int j = 0; j < n; j++){
            g[i][j] = min(g[i][j], d(p[i], p[j]));  //行走
        }
        //cout << endl;
    }
    dijkstra();
    cout << (int)(dist[1] + 0.5) << endl;
    return 0;
}

AcWing 4249. 电车

题目链接

4249. 电车 - AcWing题库

题解思路

Floyd算法（可求任何两个节点间的最短距离、基于动态规划）

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
#include <bits/stdc++.h>
using namespace std;
int d[110][110];
int main ()
{
    int n, a, b;
    cin  >> n >> a >> b;
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= n; i++){
        int k, x;
        cin  >> k;
        for(int j = 0; j < k; j++){
            cin  >> x;
            if(j == 0)d[i][x] = 0;      //第一个点需要的步数为0
            else d[i][x] = 1;           //其他点需要的步数为1
        }
    }
    //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]);
            }
        }
    }
    if(d[a][b] == 0x3f3f3f3f)cout << -1 << endl;
    else cout << d[a][b] <<endl;
    return 0;
}

AcWing 4251. Nya图最短路

题目链接

4251. Nya图最短路 - AcWing题库

题解思路

普通建图的话，如果只有两层数据拉拉满，建图直接爆

在每一层建立虚拟节点,这个点到其他层源点都是0,这个点到本层源点都是c,相当于这个相邻其他层到本层就是c

然后dj，或者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
#include <bits/stdc++.h>
#define pii pair<int, int>
const  int N = 200010, M = 500010;
using namespace std;
int n, m, c;
int h[N], e[M], ne[M], w[M], d[N], idx;
bool st[N];
void add(int a, int b, int z){
    e[idx] = b, w[idx] = z, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra(){
    memset(d, 0x3f, sizeof d);
    memset(st, false, sizeof st);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    d[1] = 0;
    pq.push({0, 1});
    while(pq.size()){
        int x = pq.top().second;
        pq.pop();
        if(st[x] == true)continue;
        st[x] = true;
        for(int i = h[x]; ~i; i = ne[i]){
            int j = e[i];
            if(d[j] > d[x] + w[i]){
                d[j] = d[x] + w[i];
                pq.push({d[j], j});
            }
        }
    }
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main ()
{
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++){
        cin >> n >> m >> c;
        int cur = n + 10; idx = 0;
        memset(h, -1, sizeof h);
        //在每一层建立虚拟节点,这个点到其他层源点都是0,这个点到本层源点都是c,相当于这个相邻其他层到本层就是c
        for(int i = 1; i <= n; i++){
            int lev;
            cin >> lev;
            add(i, cur + lev - 1, 0); //这个点到其他层源点都是0
            add(i, cur + lev + 1, 0);
            add(cur + lev, i, c);       //这个点到本层源点都是c，相当于这个相邻其他层到本层就是c
        }
        for(int i = 1; i <= m; i++){
            int x, y, z;
            cin >> x >> y >> z;
            add(x, y, z);
            add(y, x, z);
        }
        int res = dijkstra();
        printf("Case #%d: ", t);
        if(res == 0x3f3f3f3f)cout << -1 << endl;
        else cout << res << endl;
    }
    return 0;
}