题目大意
有一个 \(n\) 个点 \(m\) 条边的有向图组成的城市，每条边可以是骑行边或公共交通边，公共交通边只能走一条，边是从 \(u_i\) 到 \(v_i\) 的有向边，需要花费 \(time_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)}\)。
\(\texttt{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;
}