g733 - 110北二4.漫遊高譚市
題目描述
題目描述一個城市的地圖，包含兩種交通方式：步行和搭乘蝙蝠車。地圖由 n 個地點和 m1 個步行路徑、m2 個蝙蝠車路徑組成。要求計算從起點 s 到終點 t 的最短路徑長度，可以任意切換步行和蝙蝠車。
解題思路
本題可以使用 Dijkstra 演算法來求解最短路徑。由於存在兩種交通方式，因此需要為每個節點維護四個狀態：dis[node][0] 表示只使用步行到達該節點的最短路徑長度，dis[node][1] 表示步行和蝙蝠車交替到達該節點的最短路徑長度，dis[node][2] 表示從步行轉蝙蝠車到達該節點的最短路徑長度，dis[node][3] 表示只使用蝙蝠車到達該節點的最短路徑長度。
Dijkstra 演算法使用優先佇列來選擇下一個要擴展的節點，優先佇列按照路徑長度排序。在擴展節點時，需要考慮兩種交通方式，並更新相應狀態下的最短路徑長度。
複雜度分析
- 時間複雜度: O(E log V)，其中 E 是邊的數量，V 是節點的數量。
- 空間複雜度: O(V)，用於儲存距離陣列和優先佇列。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,m1,m2,x,y,v,s,t,dis[10005][4];
bool has[10005][4];
vector <pair <int,int>> E1[100005],E2[100005];//go dis
void djsk(){
priority_queue <pair <int,pair <int,int>>,vector <pair <int,pair <int,int>>>,greater <pair <int,pair <int,int>>>> pq;//dis by go
for(int i=0;i<4;++i){
pq.push({0,{i,s}});
dis[s][i]=0;
}
while(!pq.empty()){
int dt=pq.top().first,by=pq.top().second.first,g=pq.top().second.second;
pq.pop();
if(has[g][by])continue;
has[g][by]=1;
if(by!=3){//0 1 2
for(int i=0;i<E1[g].size();++i){
if(by==1){
if(dis[E1[g][i].first][2]>dis[g][by]+E1[g][i].second){
dis[E1[g][i].first][2]=dis[g][by]+E1[g][i].second;
pq.push({dis[E1[g][i].first][2],{2,E1[g][i].first}});
}
}
else{
if(dis[E1[g][i].first][by]>dis[g][by]+E1[g][i].second){
dis[E1[g][i].first][by]=dis[g][by]+E1[g][i].second;
pq.push({dis[E1[g][i].first][by],{by,E1[g][i].first}});
}
}
}
}
if(by!=2){//0 1 3
for(int i=0;i<E2[g].size();++i){
if(by==0){
if(dis[E2[g][i].first][3]>dis[g][by]+E2[g][i].second){
dis[E2[g][i].first][3]=dis[g][by]+E2[g][i].second;
pq.push({dis[E2[g][i].first][3],{3,E2[g][i].first}});
}
}
else{
if(dis[E2[g][i].first][by]>dis[g][by]+E2[g][i].second){
dis[E2[g][i].first][by]=dis[g][by]+E2[g][i].second;
pq.push({dis[E2[g][i].first][by],{by,E2[g][i].first}});
}
}
}
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m1 >> m2;
memset(dis,0x3f,sizeof(dis));
for(int i=0;i<m1;++i){
cin >> x >> y >> v;
E1[x].push_back({y,v});
E1[y].push_back({x,v});
}
for(int i=0;i<m2;++i){
cin >> x >> y >> v;
E2[x].push_back({y,v});
E2[y].push_back({x,v});
}
cin >> s >> t;
djsk();
cout << min(min(dis[t][0],dis[t][1]),min(dis[t][2],dis[t][3]));
}