给你一个有向图（n,m⩽20000n,m\leqslant 20000n,m⩽20000），现在有一些作为枢纽的点，且保证每一条边的两个点至少有一个是枢纽点，现在给q个询问，问某一个点到另一个点的最短路，你只需输出可以到达的数量，和可以到达的最短路之和
输入样例 3 3 1 21 2 102 3 102 1 521 33 1 输出样例 120 数据范围对于 30%的数据，N⩽100，M⩽2,000。N\leqslant 100，M\leqslant 2,000。N⩽100，M⩽2,000。 对于 100%的数据，1⩽N,M⩽20,000，1⩽K⩽200，1⩽Q⩽50,000，1⩽di⩽10,000。1\leqslant N,M\leqslant 20,000，1\leqslant K\leqslant 200，1\leqslant Q\leqslant 50,000， 1\leqslant d_i\leqslant 10,000。1⩽N,M⩽20,000，1⩽K⩽200，1⩽Q⩽50,000，1⩽di⩽10,000。
样例说明对于第一个航班，唯一可行的路线是1−>2−>31->2->31−>2−>3，花费 20。
解题思路因为枢纽点很少，我们对于每一个枢纽点跑一边spfaspfaspfa 如果询问的出发点是枢纽点，那就是直接最短路的值 如果不是，那和他相连的就都是，然后计算这条边加和他相连的点到终点的最短路就是结果
代码 #include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long longusing namespace std;ll n, m, k, q, x, y, z, tot, num, sum, ans, p[20010], v[20010], head[20010], b[210][20010];struct rec{ll to, l, next;}a[20010];void spfa(ll x){memset(b[v[x]], 127/3, sizeof(b[v[x]]));b[v[x]][x] = 0;//以第x个枢纽为起点到各个点的最短路p[x] = 1;queue<ll>d;d.push(x);while(!d.empty()){ll h = d.front();d.pop();for (ll i = head[h]; i; i = a[i].next)if (b[v[x]][h] + a[i].l < b[v[x]][a[i].to]){b[v[x]][a[i].to] = b[v[x]][h] + a[i].l;if (!p[a[i].to]){p[a[i].to] = 1;d.push(a[i].to);}}p[h] = 0;}}int main(){scanf("%lld%lld%lld%lld", &n, &m, &k, &q);for (ll i = 1; i <= m; ++i){scanf("%lld%lld%lld", &x, &y, &z);a[++tot].to = y;a[tot].l = z;a[tot].next = head[x];head[x] = tot;}for (ll i = 1; i <= k; ++i){scanf("%lld", &x);v[x] = i;//记录下他是第几个，方便减小内存spfa(x);}for (ll i = 1; i <= q; ++i){scanf("%lld%lld", &x, &y);sum = 200000010;if (v[x]) sum = min(sum, b[v[x]][y]);//他就是枢纽for (ll j = head[x]; j; j = a[j].next)if (v[a[j].to])sum = min(sum, a[j].l + b[v[a[j].to]][y]);//相连的枢纽if (sum <= 200000000){num++;ans += sum;}}printf("%lld\n%lld", num ,ans);return 0;}
