## Ý tưởng chính:
### + Ta sẽ dùng **BFS** để tìm khoảng cách ngắn nhất từ đỉnh 1 đến đỉnh $n$.
### + Sau đó, ta sẽ dùng **DFS** kết hợp điều kiện để tìm được đường đi thỏa mãn.
---
## Cài đặt:
### Ta sẽ dùng 1 mảng vector để lưu lại mối quan hệ giữa các đỉnh và 1 map để lưu lại trọng số của mỗi cạnh:
```cpp
int n, m;
vector<pair<int,int>> v[1e5+7]; // với v[i] là danh sách các đỉnh kề với i cùng trọng số của cạnh đó
map<pair<int,int>, int> e; // lưu trọng số của các cạnh
```
---
### Với BFS, ta sẽ dùng 1 mảng d[] để lưu lại khoảng cách từ đỉnh 1 đến các đỉnh khác.
### Thứ ta cần tìm chính là d[n]:
```cpp
int d[nmax]; // lưu khoảng cách từ đỉnh 1 đến các đỉnh khác
int mindis; // khoảng cách ngắn nhất từ đỉnh 1 đến n
void bfs(){
memset(d, -1, sizeof(d));
queue<int> V;
V.push(1);
d[1] = 0;
while(!V.empty()){
int u = V.front(); V.pop();
for(auto x: v[u]){
int t = x.first; // Ta chỉ cần quan tâm đến các đỉnh kề
if(d[t] == -1){
d[t] = d[u] + 1;
V.push(t);
}
}
}
mindis = d[n]; // khoảng cách cần tìm
}
```
---
## Đối với DFS, ta sẽ chia ra để xử lý từng phần:
### Với mỗi danh sách v[i], ta sẽ sắp xếp lại tăng dần theo trọng số để đảm bảo DFS tìm ra con đường có thứ tự nhỏ nhất.
Đầu tiên ta dựng một hàm so sánh trong pair:
```cpp
bool cmp(pair<int,int> x, pair<int,int> y){
return x.second < y.second; // phần tử second là trọng số
}
```
Sau đó, với mỗi đỉnh từ 1 đến n, ta sắp xếp lại danh sách các đỉnh kề:
```cpp
for(int i = 1; i <= n; ++i){
sort(v[i].begin(), v[i].end(), cmp);
}
```
**Lưu ý:** Sau khi sắp xếp thì đoạn đường đầu tiên ta tìm thấy thỏa mãn chính là đoạn đường cần tìm.
---
### Sau khi sắp xếp, ta dựng 1 hàm DFS và 1 hàm `trace` để có thể tìm và lưu lại đường đi thỏa mãn.
Để có thể trace lại sau khi DFS, ta sẽ dùng 1 mảng t[] và 1 mảng visited[] để đánh dấu lại từng đỉnh đã thăm.
---
#### Hàm DFS ta sẽ dùng đệ quy, quay lui để xét mọi trường hợp:
```cpp
int t[nmax];
int visited[nmax];
bool found = false; // kiểm tra coi đã tìm thấy dãy thỏa mãn chưa
void dfs(int s, int h){ // ta đang xét đỉnh s và khoảng cách đi được là h
if(found) return;
if(h > mindis) return;
if(s == n){
if(h == mindis){
found = true;
trace(s);
}
return;
}
visited[s] = 1;
for(auto x: v[s]){
int u = x.first;
if(!visited[u]){
visited[u] = 1;
t[u] = s;
dfs(u, h + 1);
visited[u] = 0;
}
}
visited[s] = 0;
}
```
---
#### Đối với hàm trace, ta chỉ cần truy vết ngược lại từ đỉnh $n$ về đỉnh 1 theo các phần tử trong mảng t[]:
```cpp
void trace(int s){
vector<int> path;
while(t[s] != 0){
int x = e[{s, t[s]}];
path.push_back(x);
s = t[s];
}
for(int i = path.size() - 1; i >= 0; i--) cout << path[i] << " ";
found = true;
}
```
**Lưu ý:** Vì hàm trace() được gọi trong dfs() nên cần xây dựng hàm trace() trước hàm dfs().
---
## Sau đây là code full dành cho ai chưa nghĩ ra cách code
**Lưu ý:** Trong code này mình dùng ii thay pair<int,int>, F thay first, S thay second để code gọn hơn.
```cpp
#include <bits/stdc++.h>
#define ll long long
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int nmax = 1e5 + 7;
int n, m;
vector<ii> v[nmax];
map<ii, int> e;
// BFS
int d[nmax];
int mindis;
void bfs(){
memset(d, -1, sizeof(d));
queue<int> V;
V.push(1);
d[1] = 0;
while(!V.empty()){
int u = V.front(); V.pop();
for(auto x : v[u]){
int t = x.F;
if(d[t] == -1){
d[t] = d[u] + 1;
V.push(t);
}
}
}
mindis = d[n];
}
// Trace
int t[nmax], visited[nmax];
bool found = false;
void trace(int s){
vector<int> path;
while(t[s] != 0){
int x = e[{s, t[s]}];
path.push_back(x);
s = t[s];
}
for(int i = path.size() - 1; i >= 0; i--) cout << path[i] << " ";
found = true;
}
// DFS
void dfs(int s, int h){
if(found) return;
if(h > mindis) return;
if(s == n){
if(h == mindis){
found = true;
trace(s);
}
return;
}
visited[s] = 1;
for(auto x : v[s]){
int u = x.F;
if(!visited[u]){
visited[u] = 1;
t[u] = s;
dfs(u, h + 1);
visited[u] = 0;
}
}
visited[s] = 0;
}
bool cmp(ii x, ii y){
return x.S < y.S;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int x, y, w;
cin >> x >> y >> w;
v[x].push_back({y, w});
v[y].push_back({x, w});
e[{x, y}] = e[{y, x}] = w;
}
for(int i = 1; i <= n; ++i){
sort(v[i].begin(), v[i].end(), cmp);
}
bfs();
cout << mindis << '
';
dfs(1, 0);
}
```
### Cảm ơn mọi người đã chịu khó xem lời giải của mình ạ!
loveQA
Created at
1 likes