P3106求条

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int p,w;
}b[50005];
vector<Node>a[10005][5],c[10005][5];
int n,m,tot,val[100005],dis[10005][5];
bool bj[10005][5];
inline void work1(int x){
    if(x*2+1<=tot&&b[x*2+1].w<b[x].w&&b[x*2+1].w<b[x*2].w){
        swap(b[x*2+1],b[x]);
        work1(x*2+1);
    }
    else if(x*2<=tot&&b[x].w>b[x*2].w){
        swap(b[x],b[x*2]);
        work1(x*2);
    }
}
inline void work(int x){
    if(x!=1&&b[x].w<b[x/2].w){
        swap(b[x],b[x/2]);
        work(x/2);
    }
}
inline void dij(int p,int w,int op){
    if(w>dis[p][op]||bj[p][op]){
        return;
    }
    bj[p][op]=1;
    dis[p][op]=w;
    auto it1=a[p][op].begin();
    auto it2=a[p][3].begin();
    if(op!=3){
        for(auto it:c[p][op]){
            // cout<<(*it1).w<<' '<<(*it1).p<<' '<<(*it2).w<<endl;
            if(w-(*it1).w==dis[(*it1).p][op]){
                val[(*it2).w]--;
                it1++;
                it2++;
                continue;
            }   
            if(w+it.w>=dis[it.p][op]){
                it1++;
                it2++;
                continue;
            }
            b[++tot]={it.p,w+it.w};
            dis[it.p][op]=w+it.w;
            work(tot);
            it1++;
            it2++;
        }
    }
    else{
        for(auto it:a[p][op]){
            if(w+val[it.w]>=dis[it.p][op]){
                it1++;
                continue;
            }
            b[++tot]={it.p,w+val[it.w]};
            dis[it.p][op]=w+val[it.w];
            work(tot);
            it1++;
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        val[i]=2;
        int u,v,w1,w2;
        cin>>u>>v>>w1>>w2;
        a[u][1].push_back({v,w1});
        c[v][1].push_back({u,w1});
        a[u][2].push_back({v,w2});
        c[v][2].push_back({u,w2});
        a[u][3].push_back({v,i});
        c[v][3].push_back({u,i});
    }
    for(int i=m+1;i<=m;i++){
        val[i]=2;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            dis[i][j]=1e9;
        }
    }
    b[++tot]={n,0};
    while(tot){
        dij(b[1].p,b[1].w,1);
        swap(b[1],b[tot]);
        --tot;
        work1(1);
    }             
    b[++tot]={n,0};
    while(tot){
        dij(b[1].p,b[1].w,2);
        swap(b[1],b[tot]);
        --tot;
        work1(1);
    }
    for(int i=1;i<=m;i++){
        cout<<val[i]<<' ';
    }
    b[++tot]={1,0};
    while(tot){
        dij(b[1].p,b[1].w,3);
        swap(b[1],b[tot]);
        --tot;
        work1(1);
    }
    cout<<dis[n][3];
    return 0;
}