# Shortest Paths in Grid Graphs

## 1. Shortest Path Problem

The shortest path problem is one of the most important and fundamental problems in graph theory. It has many real-world applications, such as finding the best driving directions and finding the minimum delay route in networking.

There are mainly two variants of the problem: single-source shortest paths (SSSP) and all-pair shortest paths (APSP). The most famous algorithms for SSSP are Bellman-Ford (applicable to arbitrary weights, $O(VE)$) and Dijkstra’s (applicable to nonnegative weights,$O(V \log V+E)$); the best-known algorithms for APSP are Floyd’s in $O(V^3)$ time and Johnson’s in $O(V^2 \log V + VE)$ time, which are both applicable to arbitrary weights; for nonnegative weights, running $V$ rounds of Dijkstra’s algorithm is fine.

## 2. Grid Graph

Formally speaking, a grid graph $P_w \times P_h$ is the Cartesian product of two paths. A grid graph can be drawn in a plane as a lattice. The following figure shows a grid graph $P_5 \times P_4$. Note that the weights of the edges are omitted.

We consider the shortest path problem in grid graphs, where edges are undirected and nonnegatively weighted. Specifically, we can preprocess the graph, and then answer several queries online. Each query contains two vertices $u, v$, which asks the shortest path between $u$ and $v$. Let $n = w \times h$ denote the size of the graph $P_w \times P_h$.

One naive solution is to do nothing in preprocessing, and for each query, just run an SSSP (e.g., Dijkstra’s). The time complexity is $O(1)/O(n \log n)$.

Another solution is to compute APSP during preprocessing. If we simply run $n$ rounds of SSSP algorithm, the time complexity is $O(n^2 \log n) / O(1)$.

Here, we present a nice algorithm that achieves $O(\sqrt{n})$ time per query after $O(n^{1.5} \log n)$ preprocessing. Compared with the above naive algorithms, the $O(n^{1.5} \log n) / O(\sqrt{n})$ algorithm features a good space-time tradeoff. The basic idea is divide and conquer.

## 3. The Algorithm

Assume w.l.o.g. that $w \geq h$. Also we use ordered pair $(x, y)$ $(1 \leq x \leq w, 1 \leq y \leq h)$ to represent a vertex in $P_w \times P_h$.

We define the midline of the graph as the vertices in the $\frac{w}{2}$th column. This is how we divide subproblems. Now we solve the queries where two vertices lie on different sides of the midline. Given to vertices $u, v$ where $u$ is in the left of the midline and $v$ is in the right of the midline, then every path between $u$ and $v$ must cross the midline, though it may cross the line left and right multiple times (as the following figure shows).

Now comes the key point. For the sake of convenience we denote the vertices in the midline as $M_i$, i.e. $M_i = (\frac{w}{2}, i)$. For every vertex in midline $M_i$, run an SSSP in preprocessing stage, and stores its distance to every other vertex. How does this information help? Consider a vertex $u$ left to the midline and a vertex $v$ right to the midline, since the shortest path between them must cross the midline, we can try all vertices in the midline, and simply pick the shortest path:
$$d(u, v) = \min_{1 \leq i \leq h} d(u, M_i) + d(M_i, v).$$
Since $w \geq h$, there are at most $\sqrt{n}$ vertices in the midline, so the preprocessing time is $O(\sqrt{n} \cdot n \log n)$, and the time per query is $O(\sqrt{n})$.

How should we answer the queries where two vertices lie on the same side of the midline? Note that we can’t simply solve the problem on the subgraph left to the midline, since the shortest path might possibly, though not necessarily, cross the midline.

But this is never a problem. We can update $d(u, v)$ with $\min_{1 \leq i \leq h} d(u, M_i) + d(M_i, v)$ for each query $(u, v)$ not cross the midline, then recursively solve the problem on the left and right subgraphs.

The total preprocessing time follows this recursion:
$$T(n) = 2T(n / 2) + O(n^{1.5} \log n).$$
By the master theorem, $T(n) = O(n^{1.5} \log n)$.

## 4. Remarks

From the view of implementation, the $O(\sqrt{n})$ query time can be done very efficiently, since it just computes the minimum component of the sum of two vectors. This is SIMD- and cache-friendly. Also, since in preprocessing stage we need to run $h$ independent rounds of SSSP algorithm, the preprocessing part can be easily parallelized.

# Nordic Collegiate Programming Contest 2018 [NCPC2018] 题解

unsolved

### B. Baby Bites

solved (0:08, +1)

solved (0:17)

solved (4:55)

solved (3:23)

unsolved

unsolved

solved (0:34)

solved (1:00 +1)

solved (1:57 +2)

solved (3:07)

# 2016 China Collegiate Programming Contest Final 题解

（更新中）

### Problem A. The Third Cup is Free

#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int t,n,a[MAXN];
int main()
{
scanf("%d",&t);
int kase=0;
while(t--)
{
kase++;
printf("Case #%d: ",kase);
scanf("%d",&n);
int sum=0;
for(int i=0;i<n;i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
sort(a,a+n);
for(int i=n-3;i>=0;i-=3)
sum-=a[i];
printf("%d\n",sum);
}
return 0;
}

### Problem B. Wash

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int l, n, m;
LL w, d;
LL t1, t2;

typedef pair<LL, int> p;

int main() {
int T; scanf("%d", &T);
Rep (t, T) {
priority_queue<p, vector<p>, greater<p> > q1, q2;
scanf("%d%d%d", &l, &n, &m);
rep (i, n) {
int a; scanf("%d", &a);
w[i] = a;
q1.push({w[i], i});
}
rep (i, m) {
int a; scanf("%d", &a);
d[i] = a;
q2.push({d[i], i});
}
rep (i, l) {
LL val; int id;
tie(val, id) = q1.top(); q1.pop();
_debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
t1[i] = val;
q1.push({val+w[id], id});
}
rep (i, l) {
LL val; int id;
tie(val, id) = q2.top(); q2.pop();
_debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
t2[l-1-i] = val;
q2.push({val+d[id], id});
}
LL ans = 0;
rep (i, l) {
ans = max(ans, t1[i] + t2[i]);
}
cout << "Case #" << t << ": " << ans << endl;
}
return 0;
}

### Problem G. Pandaland

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define int LL
#undef INT_MAX
#define INT_MAX LLONG_MAX

typedef pair<int, int> pt;

struct Sol {
int n = 0;
map<pt, int> mp;
vector<pair<int, int>> edges;
vector<vector<int>> adj;

int getID(int x, int y) {
auto ptr = mp.find({x, y});
if (ptr != mp.end()) return ptr->second;
mp[{x, y}] = n;
adj.push_back({});
return n++;
}

int ans = INT_MAX / 2;
int d;
bool done;

void dijkstra(int src) {
priority_queue<pt, vector<pt>, greater<pt>> q;

fill(d, d+n, INT_MAX / 2);
d[src] = 0;
fill(done, done+n, false);
q.push({0, src});
while (q.size()) {
int u = q.top().second; q.pop();
if (done[u]) continue;
done[u] = 1;
for (int id : adj[u]) {
int v, w; tie(v, w) = edges[id];
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (d[v] < ans) q.push({d[v], v});
}
}
}
}

Sol(int t) {
int m; cin >> m;
edges.resize(m+m);
rep (i, m) {
int x1, y1, x2, y2, w;
int id1, id2;
cin >> x1 >> y1 >> x2 >> y2 >> w;
id1 = getID(x1, y1); id2 = getID(x2, y2);
edges[i<<1] = {id2, w};
edges[i<<1|1] = {id1, w};
adj[id1].push_back(i<<1);
adj[id2].push_back(i<<1|1);
}
rep (u, n) {
for (int id : adj[u]) {
int v, w;
tie(v, w) = edges[id];
edges[id].second = edges[id^1].second = INT_MAX / 2;
dijkstra(u);
ans = min(ans, d[v] + w);
edges[id].second = edges[id^1].second = w;
}
}
if (ans >= INT_MAX / 2) ans = 0;
cout << "Case #" << t << ": " << ans << endl;
}
};

int32_t main() {
int T; cin >> T;
Rep (t, T) {
Sol sol(t);
}
return 0;
}



### Problem I. Mr. Panda and Crystal

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int m, n, k;
LL c, v;

vector<int> dep;
//   id                id  cnt
pair<int, vector<pair<int, int>>> formula;

bool flag = false;

void update(int i) {
LL tot = 0;
int id = formula[i].first;
for (auto& item : formula[i].second) {
tot += c[item.first] * item.second;
}
if (tot < c[id]) {
_debug("update %d!", formula[i].first);
c[formula[i].first] = tot;
flag = true;
}
}

LL dp;

int main() {
int T; scanf("%d", &T);
Rep (t, T) {
scanf("%d%d%d", &m, &n, &k);
Rep (i, n) {
int tp; scanf("%d", &tp);
int co = INT_MAX, va = 0;
if (tp == 0) {
scanf("%d", &va);
} else {
scanf("%d%d", &co, &va);
}
c[i] = co;
v[i] = va;
}
_debug("!");
rep (i, k) {
int x, y;
scanf("%d%d", &x, &y);
formula[i].first = x;
formula[i].second.resize(y);
rep (j, y) {
int u, v;
scanf("%d%d", &u, &v);
formula[i].second[j] = {u, v};
}
}
_debug("!");
do { // bellman-ford
flag =  false;
rep (i, k) update(i);
} while (flag);
memset(dp, 0, sizeof dp);
Rep (i, n) {
for (int w = c[i]; w <= m; w++) {
dp[w] = max(dp[w], dp[w - c[i]] + v[i]);
}
}
printf("Case #%d: %d\n", t, int(dp[m]));
}
return 0;
}

### Problem L. Daylight Saving Time

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;

enum {
A, B, C, D
};

const int  mday = { 0,
31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

int type = A;
int yy = 2007, mm = 1, dd = 1;
int wday = 1;

bool isleap(int y) {
if (y % 4 == 0  && y != 2100) return true;
return false;
}

void adv_year() {
yy++;
}

void adv_month() {
mm++;
if (mm > 12) {
mm = 1;
adv_year();
}
}

int advan() {
dd++;
wday ++;
if (wday > 7) wday = 1;
int mmday = mday[mm];
if (mm == 2 && isleap(yy)) mmday++;
if (dd > mmday) {
dd = 1;
adv_month();
}
if (mm == 3 && wday == 7 && dd > 7 && dd <= 14) {
type = C;
return B;
}
if (mm == 11 && wday == 7 && dd <= 7) {
type = A;
return D;
}
return type;
}

string genstr() {
char buf;
sprintf(buf, "%04d-%02d-%02d", yy, mm, dd);
return string(buf);
}

map<string, int> m;

void prep() {
m[genstr()] = type;
do {
int tp = advan();
m[genstr()] = tp;

} while (yy <= 2100);
}

int main() {
prep();
string str;
char tim;
int hh;
int T;
cin >> T;
Rep(t, T) {
cin >> str >> tim;
sscanf(tim, "%d", &hh);
switch (m[str]) {
case A:
printf("Case #%d: PST\n", t);
break;
case B:
if (hh < 2) {
printf("Case #%d: PST\n", t);
} else if (hh >= 3) {
printf("Case #%d: PDT\n", t);
} else {
printf("Case #%d: Neither\n", t);
}
break;
case C:
printf("Case #%d: PDT\n", t);
break;
case D:
if (hh < 1) {
printf("Case #%d: PDT\n", t);
} else if (hh >= 2) {
printf("Case #%d: PST\n", t);
} else {
printf("Case #%d: Both\n", t);
}
break;
}
}
return 0;
}

# 2017-2018年问题求解（三）期末上机考试 Day2 题解

### D. 旅游路线

• 部分数据满足 $latex 1≤n≤20, 1≤m≤100, 1≤s_i≤5, 1≤k_i, c≤1000$;
• 部分数据满足 $latex 1≤n≤1000, 1≤m≤50000, 1≤s_i≤200, 1≤k_i, c≤1000$;
• 部分数据满足 $latex 1≤n≤30000, 1≤m≤2*10^5, s_i=1, 1≤k_i, c≤1000$;
• 部分数据满足 $latex 1≤n≤5000, 1≤m≤2*10^5, 1≤s_i≤50, 1≤k_i, c≤1000$。