dijstra的拓展应用

dijstra的松弛操作的条件一般不变
当==也要进行操作时，else if即可（具体见代码）

一般操作是在松弛内进行的

#include<bits/stdc++.h>
using namespace std;
int const N=5e2+7;
int const M=25e4+7;
struct node{
    int a,next,len;
}e[M<<1];
int cnt,head[N];
void add(int x,int y,int len){
    e[++cnt].a =y;
    e[cnt].len =len;
    e[cnt].next =head[x];
    head[x]=cnt;
}
struct L{
    int a,dis;
    friend bool operator<(L a,L b){
        return a.dis > b.dis ;
    }
};
int vis[N],dis[N],maxn[N],num[N],pre[N],last[N],w[N];
void dijstra(int s){
    memset(pre,-1,sizeof pre);
    memset(dis,0x3f,sizeof dis);
    priority_queue<L>pq;num[s]=1;maxn[s]=w[s];
    pq.push((L){s,0});dis[s]=0;pre[s]=-1;
    while(!pq.empty()){
        int u=pq.top().a;pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next){
            if(dis[u]+e[i].len <dis[e[i].a ]){
                dis[e[i].a ]=dis[u]+e[i].len ;
                pq.push((L){e[i].a ,dis[e[i].a ]});
                num[e[i].a ]=num[u];
                maxn[e[i].a ]=maxn[u]+w[e[i].a ];
                pre[e[i].a ]=u;
            }
            else if(dis[u]+e[i].len ==dis[e[i].a ]){   //
                if(maxn[u]+w[e[i].a ]>maxn[e[i].a ]){
                    pre[e[i].a ]=u;
                    maxn[e[i].a ]=maxn[u]+w[e[i].a ];
                }
                num[e[i].a ]+=num[u];
            }
        }
    }
}
int n,m,s,d;
int main(){
    cin >> n >> m >> s >> d;
    memset(e,-1,sizeof e);
    memset(head,-1,sizeof head);
    for(int i=0;i<=n-1;++i) {
        cin >> w[i];
    }
    for(int i=1,a,b,c;i<=m;++i){
        cin >> a >> b >> c;
        add(a,b,c);add(b,a,c);
    }
    dijstra(s);
    cout << num[d] << " " << maxn[d] << "\n";
    cnt=0;
    for(int i=d;i!=-1;i=pre[i]){
        last[++cnt]=i;
    }
    for(int i=cnt;i>=1;--i){
        cout << last[i];
        if(i!=1) cout << " ";
    }
    return 0;
}