## SGraph - Editorial

### Subtask 1

Đây có thể coi như một đồ thị vô hướng.

Gọi $d_i$ là đường đi ngắn nhất từ $1$ tới $i$, kết quả của bài toán sẽ là $d_i*2$ với mỗi $i$. Lưu ý trường hợp không đi được tới $i$.

### Subtask 2

Gọi $d_i$ là đường đi ngắn nhất từ $1$ tới $i$, dùng các cạnh có dạng $(u,v,w)$. Tức là sử dụng nguyên các cạnh trong $input$.

Gọi $f_i$ là đường đi ngắn nhất từ $1$ tới $i$, dùng các cạnh có dạng $(v,u,w)$. Tức là ta đảo vị trí $u,v$, hay đảo chiều cạnh trong $input$ lại.

Ta nhận xét rằng đường đi từ $1$ tới $i$ rồi quay về $1$ chính là $f_i + d_i$.

Vậy kết quả của bài toán chính là $f_i + d_i$, với mỗi $i$. Lưu ý trường hợp $f_i$ hoặc $d_i$ không tồn tại.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2e5+5;
struct edge {
	int v,w;
};
vector<edge> a[N],b[N];
struct vcl {
	int u,du;
	bool operator < (const vcl &o) const {
		return du > o.du;
	}
};
int n,m;
int d[N],c[N];
bool mini (int &a, int b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
void dijkstra (vector<edge> *a, int *d) {
	for (int i=1; i<=n; i++) d[i] = 1e18;
	d[1] = 0;
	priority_queue<vcl> pq;
	pq.push({1,0});
	while (pq.size()) {
		vcl dak = pq.top();
		pq.pop();
		int u = dak.u, du = dak.du;
		if (d[u] < du) continue;
		for (auto dak  : a[u]) {
			int v = dak.v, w = dak.w;
			if (mini(d[v],d[u]+w)) {
				pq.push({v,d[v]});
			}
		} 		
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<=m; i++)  {
		int u,v,w; cin >> u >> v >> w;
		a[u].push_back({v,w});
		b[v].push_back({u,w});
	}
	dijkstra (a,d);
	dijkstra (b,c);
	for (int i=2; i<=n; i++) {
		int res = d[i] + c[i];
		if (res >= 1e18) res = -1;
		cout << res << '\n';
	}
}

</details>

## Color - Editorial

Ta xây một đồ thị $n$ đỉnh, với đỉnh $i$ nối tới $i-1$ và $i+1$ lần lượt có chi phí $L$ và $R$, đồng thời đỉnh $i$ nối tới $j$ nếu $c_i = c_j$ với chi phí là $C$.

Lúc này kết quả của bài toán là đường đi ngắn nhất từ $st$ tới $en$.

Tuy nhiên, nếu vậy trong trường hợp có nhiều $c_i$ bằng nhau, số cạnh có thể rất lớn (lên tới $n^2$), nên với $n = 10^5$ không thể qua được.

Để khắc phục điều này, ta có thể xây đỉnh ảo như sau:
- Nối đỉnh $i$ tới đỉnh $n+c_i$ với chi phí $C$.
- Nối đỉnh $n+c_i$ tới đỉnh $i$ với chi phí $0$.
- Cách nối này đảm bảo từ một đỉnh $i$ vẫn có thể đi tới đỉnh $j$ nếu $c_i = c_j$ với chi phí bằng $C$.

Sau thao tác này, ta sẽ có một đồ thị $n + max(c_i)$ đỉnh và có đúng $4*n$ cạnh. Sau đó ta thực hiện $dijkstra$ từ $st$ như bình thường.

<details>
<summary> Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int f[N];
int c[N];
int n,L,R,C;
struct edge {
	int v,w;
};
vector<edge> a[N];	
struct vcl {
	int u,du;
	bool operator < (const vcl &o) const {
		return du > o.du;
	}
};
void dijkstra (int st) {
	for (int i=1; i<=2*n; i++) f[i] = 1e18;
	f[st] = 0; 
	priority_queue<vcl> pq;
	pq.push({st,f[st]});
	while (pq.size()) {
		vcl dak = pq.top();
		pq.pop();
		int u = dak.u, du =dak.du;
		if (du > f[u]) continue;
		for (auto x : a[u]) {
			int v = x.v, w = x.w;
			if (f[v] > f[u] + w) {
				f[v] = f[u] + w;
				pq.push({v,f[v]});
			}
		}
	}	
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> L >> R >> C;
	vector<int> v;
	int st,en; cin >> st >> en;
	for (int i=1; i<=n; i++) {
		cin >> c[i]; v.push_back(c[i]);
	}
	sort (v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for (int i=1; i<=n; i++) {
		c[i] = lower_bound (v.begin(),v.end(),c[i]) - v.begin() + 1;
		a[c[i]+n].push_back({i,0});
		a[i].push_back({c[i]+n,C});
		if (i+1 <= n)a[i].push_back({i+1,R});
		if (i-1 >= 1)a[i].push_back({i-1,L});
	}
	dijkstra(st);
	cout << f[en];
}

</details>

## BeutyRoads - Editorial

### Subtask 1

Sinh nhị phân các cạnh sẽ sử dụng rồi kiểm tra xem có thể đi từ $1$ tới $n$ hay không, sau đó $update$ với kết quả.

### Subtask 2

Ta có một nhận xét rằng, nếu ta xây một đồ thị mới gồm $n$ đỉnh và chỉ dùng những cạnh xuất hiện trong ít nhất một đường đi ngắn nhất (và định hướng lại chúng) thì ta sẽ thu được một $DAG$, hay một đồ thị có hướng không có chu trình.

Để xây được đồ thị mới này, đầu tiên ta $dijkstra$ từ $1$, sau đó tiến hành $dfs$ từ $1$ như sau:

void dfs (int u) {
    vis[u] = 1;
    for (int i=0; i<adj[u].size(); i++) {
        int v = adj[u][i].v; int w = adj[u][i].l;
        if (d[v] == d[u] + w){
             e[u].push_back({v,w,adj[u][i].b}); if (!vis[v])dfs (v); 
        }
    }
    topo.push_back(u);
}

Ở đây, $e$ là tập cạnh của đồ thị mới và $topo$ là $vector$ lưu thứ tự $topo$ của đồ thị mới. Lưu ý sau khi tiến hành $dfs$ xong ta cần $reverse$ mảng $topo$ lại để thu được thứ tự $topo$ chính xác.

Công việc còn lại sẽ chỉ là quy hoạch động trên đồ thị $DAG$ mới, bởi mọi cạnh ta dùng sẽ đều nằm trong ít nhất một đường đi ngắn nhất nào đó.

Đặt $f_u$ là độ đẹp lớn nhất để đi theo đường đi ngắn nhất từ $1$ tới $u$, với mọi $v \in e_u$, ta sẽ cập nhật $f_v = max (f_v, f_u + beuty(u,v))$, với $beuty(u,v)$ là độ đẹp của đường đi từ $u$ tới $v$. Chú ý ta sẽ duyệt các đỉnh $u$ theo thứ tự $topo$, nói cách khác là $for$ $u \in topo$.

Ta cũng có thể tính trực tiếp mảng $f$ khi dùng $dijkstra$, tuy nhiên nên sử dụng cách $DAG$ để hiểu bản chất và đây cũng là một kĩ thuật được dùng nhiều trong các bài $dijkstra$.

<details>
<summary>Code</summary>

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N = 2e5+5;
struct edge {
	int v,l,b;
};
vector<edge> adj[N];
struct vcl {
	int u,val;
	bool operator < (const vcl &o) const {
		return val > o.val;
	}
};
int d[N];
bool mini (int &a, int b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
void dijkstra (int st) {
	priority_queue<vcl> pq;
	memset (d,0x3f3f3f,sizeof(d));
	const int inf = d[0];
	d[st] = 0;
	pq.push({st,d[st]});
	while (pq.size()) {
		vcl dak = pq.top();
		pq.pop();
		int u = dak.u, val = dak.val;
	//	cout << u << ' ' << val << '\n';
		if (val > d[u]) continue;
		for (auto x : adj[u]) {
			int v = x.v, w = x.l;
			if (mini(d[v],d[u]+w)) {
				pq.push({v,d[v]});
			}
		} 
	}
	if (d[n] == inf) d[n] = -1;
}
bool vis[N];
vector<int> topo;
vector<edge> e[N];
void dfs (int u) {
    vis[u] = 1;
    for (int i=0; i<adj[u].size(); i++) {
        int v = adj[u][i].v; int w = adj[u][i].l;
        if (d[v] == d[u] + w){
             e[u].push_back({v,w,adj[u][i].b}); if (!vis[v])dfs (v); 
        }
    }
    topo.push_back(u);
}
int f[N];
void solve () {
	topo.clear();
	for (int i=1; i<=n; i++) {
		f[i] = 0;
		adj[i].clear();
		vis[i] = false;
	}
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		int u,v,l,b; cin >> u >> v >> l >> b;
		adj[u].push_back({v,l,b});
		adj[v].push_back({u,l,b});
	}
	dijkstra(1);
	if (d[n] == -1) {
		cout << -1 << endl;
		return;
	}
	dfs(1);
	reverse(topo.begin(),topo.end());
	for (auto u : topo) {
		for (auto x : e[u]) {
			int v = x.v, b = x.b;
			f[v] = max (f[v],f[u] + b);
		}
	}
	cout << d[n] << ' ' << f[n] << endl;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

</details>

## SPath

Ta dùng phương pháp chia để trị để giải quyết bài toán này.

Xét đoạn mã sau:

void solve (tập S, cực trái l, cực phải r) {
        if (r > l hoặc tập S rỗng) return
        int mid = (r+l)/2
        for (int i=1; i<=n; i++) {
            dijkstra (l,r,i,mid) (thực hiện thuật toán dijkstra từ ô (i,mid) ra tất cả các ô có cột trong đoạn [l,r])
            Cập nhật mọi truy vấn trong tập S, giả định rằng đường đi tối ưu từ (x,y) --> (u,v) sẽ đi qua ô (i,mid)
         }
         Tập trái = những truy vấn trong tập s có max(y,v) < mid
         Tập phải = những truy vấn trong tập s có min(y,v) > mid
         solve (Tập trái, l, mid-1)
         solve (Tập phải, mid+1, r)
}

Như vậy, với mỗi lần đệ quy, ta sẽ $dijkstra$ $n$ lần. Tuy nhiên, mỗi lần thực hiện $dijkstra$ ta chỉ giới hạn trong đoạn $[l,r]$. Tức thực tế, ta chỉ cần $dijkstra$ qua tổng cộng $n*m*log_n$ ô.

Tuy vậy 

Với trường hợp này (hai ô màu xanh lá là truy vấn đang xét, hai đường thẳng màu đỏ là hai biên, đường thẳng màu cam là hàng $mid$, đường đi màu xanh nước biển là đường đi tối ưu), ta nhận thấy rằng việc chỉ $dijkstra$ trong khoảng $[l,r]$ dẫn tới việc các ô trong hàng $mid$ không thể đi theo đường màu xanh nước biển để tạo ra đường đi tối ưu, liệu nó có dẫn tới việc không thể cập nhật kết quả tối ưu? Câu trả lời là không. Thật vậy, ở lần đầu ta gọi hàm $solve(S,1,n)$, không thể có đường đi nào ra ngoài bảng. Tiếp theo tới đệ quy cho tập con trái, giả sử có một đường đi tối ưu phải ra ngoài khoảng $[l,mid-1]$, vậy nó buộc phải đi qua ô $mid$, tức là ta đã xét tới nó rồi. Tương tự với tập con bên phải. Như vậy hàm trên hoàn toàn đúng.
<details>
<summary> Code</summary>

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n,m,Q;	
const int M = 30050;
struct qr {
	int x,y,u,v,id;
};
int a[8][N];
int res[M];
struct vcl {
	int u,v,val;
	bool operator < (const vcl &o) const {
		return val > o.val;
	}
};
int mx[] = {0,1,-1,0};
int my[] = {1,0,0,-1};
int f[8][N];
const int inf = 2e9;
bool valid (int x, int y, int l, int r) {
	return (x >= 1 && x <= n && y >= l && y <= r);
}
void dijkstra (int l, int r, int st, int mid) {
	priority_queue<vcl> pq;
	pq.push({st,mid,0});
	for (int i=1; i<=n; i++) {
		for (int j=l; j<=r; j++) f[i][j] = inf;
	}
	f[st][mid] = 0;
	while (pq.size()) {
		vcl dak = pq.top();
		pq.pop();
		int u = dak.u, v = dak.v, val = dak.val;
		if (val > f[u][v]) continue;
		for (int i=0; i<4; i++) {
			int x = u + mx[i];
			int y = v + my[i];
			if (!valid(x,y,l,r)) continue;
			if (f[x][y] > f[u][v] + a[x][y]) {
				f[x][y] = f[u][v] + a[x][y];
				pq.push({x,y,f[x][y]});
			}
		}
	}
}
void solve (vector<qr> s, int l, int r) {
	if (s.size() == 0 || (l > r)) return;
	int mid = (r+l) >> 1;
	for (int i=1; i<=n; i++) {
		dijkstra (l,r,i,mid);
		for (qr dak : s) {
			int x = dak.x, y = dak.y, u = dak.u, v = dak.v;
			int id = dak.id;
			res[id] = min (res[id],f[x][y]+f[u][v]+a[i][mid]);
		}
	}
	vector<qr> lef,rig;
	for (qr dak : s) {
		int x = dak.x, y = dak.y, u = dak.u, v = dak.v;
		int id = dak.id;
		if (max(y,v) < mid) lef.push_back(dak);
		if (min(y,v) > mid) rig.push_back(dak);
	}
	solve (lef,l,mid-1);
	solve (rig,mid+1,r);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) cin >> a[i][j];
	}
	vector<qr> s;
	cin >> Q;
	for (int i=1; i<=Q; i++) {
		int x,y,u,v; cin >> x >> y >> u >> v;
		s.push_back({x,y,u,v,i});
		res[i] = 2e9;
	}
	solve (s,1,m);
	for (int i=1; i<=Q; i++){
		cout << res[i] << '\n';
	}
}

</details>