【题解】[2023合肥蜀山初中] 旅行(travel)

题目传送门

题目大意

有一个 $n$ 个点 $m$ 条边的有向图组成的城市，每条边可以是骑行边或公共交通边，公共交通边只能走一条，边是从 $u_i$ 到 $v_i$ 的有向边，需要花费 $tim{e}_i$ 的时间，求 $1$ 到其他点的最短路径。

思路分析

有一个很巧妙的思路叫分层图，它的思路是因为只能经过至多 $1$ 条公共交通边，所以可以只连骑行边，把图复制一遍，得到两层图。公共交通边作为两层图的连接的边，第一层图的 $u$ 连接第二层的 $v$，连一张单向边。这样做保证了只经过一条公共交通边，因为在第一层跑最短路，经过一条公共交通边后，会在第二层图跑最短路，到第二层图后就永远不会到第一层，也就不会经过多次公共交通边了。

考虑如何实现，我们认为第一张图是 $1$ ~ $i$ ~ $n$，第二张图是 $n+1$ ~ $n+i$ ~ $n+n$，建骑行边就是 $u\to v$ 和 $u+n\to v+n$，在两张图上建，公共交通边就是 $u\to v+n$，第一层图的 $u$ 连接第二层的 $v$，再在图上跑 dijkstra 就行，朴素和堆优化均可。

这里就写堆优化了，时间复杂度 $\mathcal{O}(m\log m)$。

$\text{code}$

/*Written by smx*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define QAQ cout<<"QAQ";
const int MAXN=4e5+5,inf=1e18,mod=1e9+7;
vector<pair<int,int> > g[MAXN];
int n,m;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
int dis[MAXN],vis[MAXN];
void dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
pq.push(make_pair(0,s));
while(!pq.empty()){
pair<int,int> k=pq.top();
pq.pop();
if(vis[k.second]) continue;
vis[k.second]=1;
for(int i=0;i<g[k.second].size();i++){
int to=g[k.second][i].first;
int w=g[k.second][i].second;
if(dis[to]>k.first+w){
dis[to]=k.first+w;
pq.push(make_pair(dis[to],to));
}
}
}
for(int i=1;i<=n;i++){
dis[i]=min(dis[i],dis[i+n]);
}
}
signed main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,op,t;
cin>>u>>v>>op>>t;
if(op==1){
g[u].push_back(make_pair(v,t));
g[u+n].push_back(make_pair(v+n,t));
}else{
g[u].push_back(make_pair(v+n,t));
}
}
dijkstra(1);
for(int i=2;i<=n;i++){
if(dis[i]==0x3f3f3f3f3f3f3f3f){
cout<<"-1 ";
}else{
cout<<dis[i]<<" ";
}
}
return 0;
}

原文地址：https://blog.csdn.net/shimingxin1007/article/details/142992966

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！