codeforces-#675-D

codeforces-#675-D

十月 18, 2020

D. Returning Home

  • 题意

给出一个n×n的网格图(n<1e5)

要求从$(S_x,S_y)$走到$(F_x,F_y)$

只能上下左右走格子 消耗一单位体力

有m<1e5个特殊点

若当前位置处于和m个特殊点中某一个同一行或同一列

则可以从这个位置瞬移到这个特殊点 瞬移不耗费体力

问最少消耗多少体力

  • 题解

特殊点的存在使得一行或者一列等效成一个点

  • 将特殊点所在列中的点等效成同一点时

从某个特殊点到达下一个相邻的特殊点所需要的体力=两个特殊点的行数差

  • 将特殊点所在行中的点等效成同一点时

从某个特殊点到达下一个相邻的特殊点所需要的体力=两个特殊点的列数差

注意我们只考虑相邻两个特殊点的建边

假如特殊点有A->B,B->C 若从A->C不会比A->B->C更优

这步就优化了任意两点建边的冗余

两个相邻特殊点的最短距离出现在上述两种情况中

所以相邻特殊点需要建两条边：

将一行缩成一点在列上移动/一列缩成一点在行上移动

注意初始位置和终点可能不经过任意一个特殊点时存在最优解

所以起始点到终点需要直接建立一条边

建完图后就已经把问题转化成最短路问题 可以直接使用Dijsktra算法

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e5+5;
const ll Mod=998857459;

ll data[Max];
int main() {
    Turnoff;
    int n;cin>>n;ll sum=0,ans=0;
    for(int i=1;i<=n;i++)cin>>data[i];
    set<ll>pre;ll Psum=0;pre.insert(0);
    for(int i=1;i<=n;i++){
        Psum+=data[i];
        if(pre.count(Psum)){
            ans++;
            pre.clear();
            pre.insert(0);
            Psum=data[i];
        }
        pre.insert(Psum);
    }
    cout<<ans<<endl;
}