### Ta sẽ sử dụng mảng 2 chiều để biểu diễn khoảng cách ngắn nhất từ 1 đến điểm nào đó, gọi Dist[u][k] là khoảng cách ngắn nhất từ 1 đến 1 điểm nào đó với:
- #### k = 0: số cạnh trên đường đi đến u hiện tại là chẵn. Vì vậy khi xét các cạnh kề với nó thì ta sẽ cập nhật đường đi với chi phí là 0.
- #### 1 <= k <= 10: số cạnh trên đường đi đến u hiện tại là lẻ và trọng số của bước cuối cùng là k. Vì vậy khi xét các cạnh kề với nó thì ta sẽ cập nhật đường đi chẵn của đỉnh đang xét với chi phí là k * trọng số cạnh hiện tại đang xét.
### Dùng một hàng đợi ưu tiên lưu đỉnh và khoảng cách và trọng số cạnh trước đó để tính chi phí đi từ a đến b đến c.
# Code:
```ruby
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
const int oo=1e18;
struct edge{
int v,w;
};
struct Node{
int u,distu,W;
bool operator<(const Node &a) const{
return distu>a.distu;
}
};
int n,m,ans,dist[maxn][12];
vector<edge> g[maxn];
void dijkstra(){
for (int i=0;i<maxn;i++)
for (int j=0;j<12;j++) dist[i][j]=oo;
dist[1][0]=0;
priority_queue<Node> pq;
pq.push({1,0,0});
while(!pq.empty()){
Node x=pq.top();
pq.pop();
int u=x.u;
int d=x.distu;
int k=x.W;
if (d>dist[u][k]) continue;
for (auto [v,w]:g[u]){
if (k==0){
if (d<dist[v][w]){
dist[v][w]=d;
pq.push({v,d,w});
}
} else{
int nd=d+k*w;
if (dist[v][0]>nd){
dist[v][0]=nd;
pq.push({v,nd,0});
}
}
}
}
ans=dist[n][0];
}
signed main(){
cin>>n>>m;
for (int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dijkstra();
cout<<(ans==oo?-1:ans);
}
```
bacnewbie
Created at
0 likes