手机网站跟PC端网站有啥区别,文库类网站建设建议及经验,wordpress怎么给别人建站,怎么做网站简单的假期计划
jzoj 3936
题目大意
给你一个有向图#xff08;n,m⩽20000n,m\leqslant 20000n,m⩽20000#xff09;#xff0c;现在有一些作为枢纽的点#xff0c;且保证每一条边的两个点至少有一个是枢纽点#xff0c;现在给q个询问#xff0c;问某一个点到另一个点的最短…假期计划
jzoj 3936
题目大意
给你一个有向图n,m⩽20000n,m\leqslant 20000n,m⩽20000现在有一些作为枢纽的点且保证每一条边的两个点至少有一个是枢纽点现在给q个询问问某一个点到另一个点的最短路你只需输出可以到达的数量和可以到达的最短路之和
输入样例
3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1输出样例
1
20数据范围
对于 30%的数据N⩽100M⩽2,000。N\leqslant 100M\leqslant 2,000。N⩽100M⩽2,000。 对于 100%的数据1⩽N,M⩽20,0001⩽K⩽2001⩽Q⩽50,0001⩽di⩽10,000。1\leqslant N,M\leqslant 20,0001\leqslant K\leqslant 2001\leqslant Q\leqslant 50,000 1\leqslant d_i\leqslant 10,000。1⩽N,M⩽20,0001⩽K⩽2001⩽Q⩽50,0001⩽di⩽10,000。
样例说明
对于第一个航班唯一可行的路线是1−2−31-2-31−2−3花费 20。
解题思路
因为枢纽点很少我们对于每一个枢纽点跑一边spfaspfaspfa 如果询问的出发点是枢纽点那就是直接最短路的值 如果不是那和他相连的就都是然后计算这条边加和他相连的点到终点的最短路就是结果
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using 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;queuelld;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;
}
