观光

题目描述：

n个点，m条有向边，起点s，终点f，假设s到f的最短路距离为dis,问s到f的路径中权值为dis和dis-1的数量

思路：

同样是最短路计数问题，不过这个题需要维护最短路和次短路

注意两种状态都要存和处理

我们用dis[i][0]表示s到i的最短路，用dis[i][1]表示s到i的次短路，每次更新的时候都拿当前状态先和最短路比较，小于就更新最小值和次小值，相等就更新最短路数量，如果都不行，再拿当前状态和次短路比较，如果小于就更新次短路，相等就更新次短路

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 20000 + 50
int n, m, k, op;
int s, t;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

struct ranran{
    int val, u, op;
    bool operator <(const ranran &x)const{
        return x.val < val;
    }
};

int dis[MAX][2];
bool vis[MAX][2];
int num[MAX][2];

void dijkstra(){
    priority_queue<ranran>q;
    mem(dis, inf);mem(vis, 0);mem(num, 0);
    dis[s][0] = 0;
    num[s][0] = 1;
    q.push({0, s, 0});
    while (!q.empty()) {
        auto [d, u, op] = q.top();q.pop();
        if(vis[u][op])continue;
        vis[u][op] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v][0] > dis[u][op] + tr[i].val){
                dis[v][1] = dis[v][0];num[v][1] = num[v][0];
                q.push({dis[v][1], v, 1});
                dis[v][0] = dis[u][op] + tr[i].val;
                num[v][0] = num[u][op];
                q.push({dis[v][0], v, 0});
            }
            else if(dis[v][0] == dis[u][op] + tr[i].val){
                num[v][0] += num[u][op];
            }
            else if(dis[v][1] > dis[u][op] + tr[i].val){
                dis[v][1] = dis[u][op] + tr[i].val;
                num[v][1] = num[u][op];
                q.push({dis[v][1], v, 1});
            }
            else if(dis[v][1] == dis[u][op] + tr[i].val){
                num[v][1] += num[u][op];
            }
        }
    }
    int ans = num[t][0] + (dis[t][0] == dis[t][1] - 1 ? num[t][1] : 0);
    cout << ans << endl;
}

void work(){
    cin >> n >> m;
    tot = 0;mem(head, 0);
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cin >> s >> t;
    dijkstra();
}



int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}