# Chữa bài dijkstra 08/08/2023

> Lưu ý:
> - Dùng `priority_queue` sẽ nhanh hơn `set`.
> - Những bài toán cần trạng thái dijkstra nhiều chiều, có thể dùng struct như sau:
>

struct state{
    int w, a, b, c, d, x, y, z....

    bool operator < (const state &a) const{
        return w > a.w;
    }
};

priority_queue<state> q;

> hoặc dùng `tuple`.

## Bài 1: [Xóa cạnh](https://marisaoj.com/problem/176)
- Trạng thái $f(i,j)$ là đường đi ngắn nhất tới $i$ và đã xóa $j$ cạnh.

Code:

:::spoiler

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 2e5 + 5;

int n, m, k;
int d[maxn][6];
vector<pi> edge[maxn];

struct state{
    int w, u, k;

    bool operator < (const state &a) const{
        return w > a.w;
    }
};

void dij(){
    setinf(d);
    priority_queue<state> q;
    d[1][0] = 0;
    q.push({0, 1, 0});

    while(q.size()){
        int w = q.top().w,
            u = q.top().u,
            K = q.top().k;
        q.pop();

        if(d[u][K] != w) continue;

        for(pi &v : edge[u]){
            if(d[v.first][K] > w + v.second){
                q.push({d[v.first][K] = w + v.second, v.first, K});
            }
            if(K < k && d[v.first][K + 1] > w){
                q.push({d[v.first][K + 1] = w, v.first, K + 1});
            }
        }
    }

    int mn = inf64;
    for(int i = 0; i <= k; i++) mn = min(d[n][i], mn);
    if(mn == inf64) cout << -1;
    else cout << mn;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int u,v , w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }

    dij();
}

:::

## Bài 2: [Đường đi ba chiều](https://marisaoj.com/problem/178)
- Trạng thái $f(x,y,z)$ là đường đi ngắn nhất tới tọa độ $(x,y,z)$.

Code
:::spoiler

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

long long n, a[107][107][107], dist[107][107][107];
bool visited[107][107][107];
struct NODE{
    long long w, x, y, z;
};
struct cmp{
    bool operator() (NODE a, NODE b){
        return a.w > b.w;
    }
};
struct VERTEX{
    int x, y, z;
};
vector<VERTEX> adj[107][107][107];

void dijkstra(int x, int y, int z){
    memset(dist, 0x3f, sizeof dist);
    memset(visited, false, sizeof visited);

    dist[x][y][z] = 0;
    priority_queue<NODE, vector<NODE>, cmp> pq;
    pq.push({dist[x][y][z], x, y, z});

    while(!pq.empty()){
        NODE u = pq.top();
        pq.pop();

        if(visited[u.x][u.y][u.z]) continue;
        visited[u.x][u.y][u.z] = true;

        for(int i = 0; i < (int) adj[u.x][u.y][u.z].size(); i++){
            VERTEX v = adj[u.x][u.y][u.z][i];
            if(dist[v.x][v.y][v.z] > dist[u.x][u.y][u.z] + a[v.x][v.y][v.z]){
                dist[v.x][v.y][v.z] = dist[u.x][u.y][u.z] + a[v.x][v.y][v.z];
                pq.push({dist[v.x][v.y][v.z], v.x, v.y, v.z});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                cin >> a[i][j][k];
                if(i > 1) adj[i][j][k].push_back({i - 1, j, k});
                if(j > 1) adj[i][j][k].push_back({i, j - 1, k});
                if(k > 1) adj[i][j][k].push_back({i, j, k - 1});

                if(i < n) adj[i][j][k].push_back({i + 1, j, k});
                if(j < n) adj[i][j][k].push_back({i, j + 1, k});
                if(k < n) adj[i][j][k].push_back({i, j, k + 1});
            }
        }
    }

    dijkstra(1, 1, 1);
    cout << dist[n][n][n] << "\n";
}

:::

## Bài 3: [Số lượng đường đi ngắn nhất](https://marisaoj.com/problem/175)
- Với $c_i$ là số lượng đường đi ngắn nhất tới $i$.
- Khi cập nhật đường đi ngắn nhất, nếu cập nhật đường đi từ $u$ sang $v$, nếu $d_u+w=d_v$, $f_v$ sẽ tăng thêm $f_u$. Trường hợp $d_u+w<d_v$, gán $f_v=1$ do từ chỉ có duy nhất đường đi ngắn nhất từ $u$ sang $v$.

Code:
:::spoiler

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

const int N = 2e5 + 5;
const long long MOD = 1e9 + 7;
typedef pair<long long, int> pli;

int n, m;
vector<pli> adj[N];
pli d[N];

void dijkstra() {
	for (int i = 2; i <= n; ++i) {
		d[i] = {LLONG_MAX, 0};
	}
	d[1] = {0, 1};
	priority_queue<pli, vector<pli>, greater<pli>> q;
	q.push({0, 1});
	while (!q.empty()) {
		long long k = q.top().first;
		int u = q.top().second;
		q.pop();
		if (d[u].first != k) {
			continue;
		}
		for (pli v: adj[u]) {
			if (d[v.second].first > k + v.first) {
				d[v.second] = {k + v.first, d[u].second};
				q.push({d[v.second].first, v.second});
			} else if (d[v.second].first == k + v.first) {
				d[v.second].second += d[u].second;
			}
			d[v.second].second %= MOD;
		}
	}
}

void fast() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int main() {
	fast();
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		long long w;
		cin >> u >> v >> w;
		adj[u].push_back({w, v});
		adj[v].push_back({w, u});
	}
	
	dijkstra();
	cout << d[n].second;
}

:::

## Bài 4: [Cạnh đôi](https://marisaoj.com/problem/177)
- Nhận thấy trọng số cạnh rất bé, ta có trạng thái là $f(i,w)$ là đường đi nhỏ nhất đến $i$ với trọng số cạnh vừa qua là $w$. Do đi 2 cạnh cùng lúc, $w > 0$ khi đã đi qua lẻ cạnh, $w=0$ khi đã đi qua chẵn cạnh.
- Từ trạng thái $f(u,w)$ với $w>0$ có thể đến trạng thái $f(v,0)$ với trọng số $w \times w_{u,v}$.
- Từ trạng thái $f(u,0)$ có thể đến trạng thái $f(v,w_{u,v})$ với cạnh trọng số $0$.
- Ví dụ xuất phát từ $1$ tới $2$ với cạnh trọng số $4$, ta đi từ $f(1, 0) = 0$ đến $f(2, 4) = 0$. Rồi đi từ $2$ tới $3$ với cạnh trọng số $5$ thì đi từ $f(2, 4)$ đến $f(3, 0) = 4 \times 5 = 20$.

Code
:::spoiler

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf =1e9;
struct Node{
	int u,dist;
};
 
struct Edge{
	int v,w;
};
 
struct cmp{
	bool operator ()(Node a, Node b){
		return a.dist > b.dist;
	}
};
 
vector <Edge> adj[200001];
bool visited[200001];
int n,m;
int d[200001]{};
int c=0;
 
 
void inp(){
	cin >> n >> m;
	for (int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
}
 
void dijsktra(){
	priority_queue<Node , vector<Node> , cmp> h;
	queue<int> q;
	memset(visited , false , sizeof(visited));
	h.push({1,0});
	for (int i=1;i<=n;i++) d[i]=inf;
	d[1]=0;
	while(h.size()){
		Node x = h.top();
		h.pop();
		if (visited[x.u]) continue;
		visited[x.u]= true;
 
		
		for (Edge k:adj[x.u])
		for (Edge e : adj[k.v]){
			if (d[e.v] > d[x.u] + e.w *k.w) {
				d[e.v] = d[x.u] + e.w *k.w;
				h.push({e.v,d[e.v]});
			}
		}
 
 
	}
}
 
void solve(){
	inp();
	dijsktra();
    
	cout << (d[n]== inf ? -1 : d[n]);
}
 
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}

:::