传送门

题意

的地图，表示可走，表示起点，终点，向上下左右走的花费都是1，有个传送阵，可以传送到对应的点，花费为3。问到终点的花费最少是多少。

分析

经典的为题，只需要构造一个优先队列，存放路径和步数，用map映射下传送阵的坐标。然后标记是否访问过点即可。

时间复杂度：

参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

int const maxn = 300 + 10;
struct node {
    int x, y, step;
    node(const int &x = 0, const int &y = 0, const int &step = 0) : 
        x(x), y(y), step(step) {}
    bool operator<(const node & obj) const {
        return step > obj.step;
    }
};

map<pair<int,int>,pair<int,int>> mv;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n, m, q; 
int vis[maxn][maxn];
char mp[maxn][maxn];

bool check(int tx, int ty) {
    if (tx <= 0 || ty <= 0 || tx > n || ty > m) return false;
    return true;
}

int bfs(int sx, int sy) {
    priority_queue<node> q;
    q.emplace(sx, sy, 0);
    while (!q.empty()) {
        int x = q.top().x, y = q.top().y;
        int s = q.top().step;
        q.pop();
        if (vis[x][y]) {
            continue;
        }
        vis[x][y] = 1;
        if (mp[x][y] == 'T') {
            return s;
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (check(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
                q.emplace(tx, ty, s + 1);
            }
        }
        if (mv.count({x, y})) {
            int tx = mv[{x, y}].first;
            int ty = mv[{x, y}].second;
            if (check(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
                q.emplace(tx, ty, s + 3);
            }
        }
    }
    return -1;
}

int main(void) {
    FAST_IO;

    while (cin >> n >> m >> q) {
        memset(vis, 0, sizeof(vis));
        mv.clear();
        int x, y;
        for (int i = 1; i <= n; i++) {
            cin >> mp[i] + 1;
            for (int j = 1; j <= m; j++) {
                if (mp[i][j] == 'S') {
                    x = i, y = j;
                }
            }
        }
        while (q--) {
            int x, y, u, v;
            cin >> x >> y >> u >> v;
            x++, y++, u++, v++;
            mv[{x, y}] = {u, v};
        }
        int ans = bfs(x, y);
        cout << ans << endl;
    }

    return 0;
}