观光

基本与单源最短路的套路相同，注意更新方案数并维护次短最短即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,l,r) for (int i=(l);i<=(r);++i)
#define REP(i,l,r) for (int i=(l);i<(r);++i)
#define RFOR(i,l,r) for (int i=(l);i>=(r);--i)
#define RREP(i,l,r) for (int i=(l);i>(r);--i)
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3fLL;
inline void readi(int &p){
    p=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
    p=f*p;
}
inline void readl(ll &p){
    p=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
    p=f*p;
}

struct node{
    int Next,y,v;
}Pth[10005];
int head[1005],cnt;
inline void add(int x,int y,int v){
    cnt++;
    Pth[cnt].Next=head[x];
    Pth[cnt].y=y;
    Pth[cnt].v=v;
    head[x]=cnt;
}

int n,m,s,f;
int d[1005][2],c[1005][2];
bool v[1005][2];
struct heap{
    int v,x,ty;
    bool operator < (const heap &b) const{
        return v>b.v;
    }
}S;
void dij(){
    priority_queue <heap> q;
    q.push({0,s,0});
    while (!q.empty()){
        heap t=q.top(); q.pop();
        int x=t.x,ty=t.ty;
        if (v[x][ty]) continue;
        v[x][ty]=1;
        for (int i=head[x];i;i=Pth[i].Next){
            int y=Pth[i].y;
            int z=t.v+Pth[i].v;
            if (d[y][0]>z){
                if (d[y][1]>d[y][0]){
                    d[y][1]=d[y][0];
                    c[y][1]=c[y][0];
                    q.push({d[y][1],y,1});
                }
                d[y][0]=z;
                c[y][0]=c[x][ty];
                q.push({d[y][0],y,0});
            }else if (d[y][0]==z){
                c[y][0]+=c[x][ty];
            }else if (d[y][1]>z){
                d[y][1]=z;
                c[y][1]=c[x][ty];
                q.push({d[y][1],y,1});
            }else if (d[y][1]==z){
                c[y][1]+=c[x][ty];
            }
        }
    }
}

void solve(){
    cnt=0; memset(head,0,sizeof head);
    readi(n); readi(m);
    FOR(i,1,m){
        int x,y,c;
        readi(x),readi(y),readi(c);
        add(x,y,c);
    }
    readi(s),readi(f);
    memset(d,0x3f,sizeof d);
    memset(c,0,sizeof c);
    memset(v,0,sizeof v);
    d[s][0]=0,c[s][0]=1;
    dij();
    if (d[f][0]+1==d[f][1]) printf("%d\n",c[f][0]+c[f][1]);
    else printf("%d\n",c[f][0]);
}

int main(){
    int t; readi(t);
    while (t--) solve();
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF&%E6%AC%A1%E7%9F%AD%E8%B7%AF/