huring
0%

凌波微步

Posted on Edited on In

题目：
你在一个二维空间里的(𝑥𝑀𝑒,𝑦𝑀𝑒)位置，你的家在(𝑥𝐻𝑜𝑚𝑒,𝑦𝐻𝑜𝑚𝑒)位置。每一秒钟你可以选择从你当前位置向上下左右四个方向之一移动一个单位。你现在归心似箭，觉得这么走很慢，所幸你有技能“凌波微步”，在这片二维空间中，有3对传送门，每一对传送门以(𝑥𝑠,𝑦𝑠,𝑥𝑡,𝑦𝑡)的形式给出，表示你到达(𝑥𝑠,𝑦𝑠)点就可以发动“凌波微步”技能，花费10秒钟到达(𝑥𝑡,𝑦𝑡)点，相反你也可以花费10秒钟从(𝑥𝑡,𝑦𝑡)点发动“凌波微步”技能到达(𝑥𝑠,𝑦𝑠)点。“凌波微步”技能可以无限多次发动，但只能在所给出的3对传送门之间使用。请问你回家最短用时多少秒。

输入
输入第一行4个整数，依次是xMe、yMe、xHome、yHome，表示当前你的位置和你家的位置。
接下来三行，每行描述一对传送门(xs, ys, xt, yt)，含义见题面（0 <= xi, yi <= 10^9）
输出
输出仅一行，包含一个整数表示回家的最少用时
输入样例
0 0 20 20
1 1 18 20
1000 1003 1000 1004
1000 1005 1000 1006
输出样例
14
解法:
最短路径的一个变形，就坐标映射为点就可以
代码:

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
struct Node
{
    int to;
    long long  len;
    bool  operator<(const Node &a) const
    {
        return len  > a.len;
    }
};
struct xy
{
    int x;
    int y;
    bool  operator<(const xy &a) const
    {
        if(x == a.x)
            return y < a.y;
        else
        {
            return x < a.x;
        }
        
    }
};
bool isUsed[510];
long long ans[510];
vector<Node> NodeQueue[510];
void addEdge(int s, int e, int len)
{
    NodeQueue[s].push_back((Node){e,len});
    NodeQueue[e].push_back((Node){s,len});
}
map<xy,int> m;
priority_queue<Node> PriNodeQueue;

int main()
{
    int sum = 0;
    int xme, yme, xhome, yhome;
    scanf("%d%d%d%d", &xme, &yme, &xhome, &yhome);
    m[(xy){xme,yme}] = sum++;
    m[(xy){xhome,yhome}] = sum++;
    addEdge(0,1,abs(xme-xhome) + abs(yme - yhome));
    for(int i = 1; i < 4; i++)
    {   
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        map<xy,int> :: iterator it;
        if(m.find((xy){x1,y1}) == m.end()){
            sum++;
            for(it = m.begin(); it != m.end(); it++)
            {
                int v = (*it).second;
                addEdge(sum,v,abs(x1-(*it).first.x) + abs(y1-(*it).first.y));
            }
            m[(xy){x1,y1}] = sum;
        }
        if(m.find((xy){x2,y2}) == m.end())
        {
            sum++;
            for(it = m.begin(); it != m.end(); it++)
            {
                int v = (*it).second;
                addEdge(sum,v,abs(x2-(*it).first.x) + abs(y2-(*it).first.y));
            }
            m[(xy){x2,y2}] = sum;
        }
        int l = abs(x1-x2) + abs(y1-y2);
        addEdge(m[(xy){x1,y1}],m[(xy){x2,y2}],min(10,l));
    }
    for(int i = 0; i < 10; i++)
        ans[i] = 9999999999;
    ans[0] = 0;
    PriNodeQueue.push((Node){0,0});
    while(!PriNodeQueue.empty()){
        Node now = PriNodeQueue.top();
        PriNodeQueue.pop();
        int u = now.to;
        if(!isUsed[u]){
            isUsed[u] = true;
           // printf("%d %d\n",u,ans[u]);
            for(int i = 0; i < NodeQueue[u].size(); i++){
                if(!isUsed[NodeQueue[u][i].to]){
                    int v = NodeQueue[u][i].to;
                    int len = NodeQueue[u][i].len;
                    if(ans[v] > ans[u] + len)
                    {
                        ans[v] = ans[u] + len;
                        PriNodeQueue.push((Node){v,ans[v]});
                    }
                }
            }
        }
    }
    printf("%lld",ans[1]);
    return 0;
    
}