solution

最短路+Dp

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
typedef long long ll;

const int N = 1010,M = 20010;

int n,m;
int S,F;

int id[N];

int idx,e[M],ne[M],w[M],h[N];
void add(int a,int b,int c){
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}

int dis[N];
bool vis[N];

void dijkstra(int S){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    priority_queue<PII,vector<PII>,greater<PII> > q;
    dis[S] = 0;
    q.push({0,S});
    while(q.size()){
        int t = q.top().second;q.pop();
        if(vis[t])continue;
        vis[t] = true;
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            if(dis[j] > dis[t] + w[i]){
                dis[j] = dis[t] + w[i];
                q.push({dis[j],j});
            }
        }
    }
}

int f[2][N];

bool cmp(int a,int b){return dis[a] < dis[b];}

void solve(){
    memset(h,-1,sizeof h);
    idx = 0;
    memset(f,0,sizeof f);
    cin>>n>>m;
    for(int i = 1,a,b,c;i<=m;i ++){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cin>>S>>F;
    dijkstra(S);
    for(int i = 1;i<=n;i ++)id[i] = i;
    sort(id+1,id+n+1,cmp);
    f[0][S] = 1;
    for(int k = 0;k<=1;k ++){
        for(int p = 1;p<=n;p ++){
            int u = id[p];
            for(int i = h[u];~i;i = ne[i]){
                int j = e[i];
                if(dis[u] + w[i] == dis[j])f[k][j] += f[k][u];
                if(k == 0 && dis[u] + w[i] == dis[j] + 1)f[1][j] += f[0][u];
            }
        }
    }
    cout<<f[0][F] + f[1][F]<<"\n";
}

int main(){
    //freopen("test.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}