题目传送门

题意简述

给定一张有向带权图，有 \(Q\) 个请求，每个请求给出点 \(a_i\)，\(b_i\)，费用为 \(a_i\) 经过点 \(1 \rightarrow K\) 中的至少一个到达 \(b_i\) 的最小权值和。求出可行的请求数和最小费用和。

分析

有多个询问，很明显是多源最短路，求多源最短路可以用 Floyd，也可以调用 \(n\) 次 Dijkstra。

核心代码

int dis[205][205];
bool vis[205][205];

void Dijkstra(int s) {
	memset(dis[s] + 1, 0x3f3f3f3f, sizeof dis[s] + 1);
	memset(vis[s] + 1, 0, sizeof vis[s] + 1);
	struct poi {
		int d, p;
		bool operator<(const poi& x)const { return d > x.d; }
	};
	priority_queue <poi>q;
	dis[s][s] = 0;
	q.push({ 0, s });
	while (!q.empty())
	{
		int u = q.top().p; q.pop();
		if (vis[s][u])continue;
		vis[s][u] = true;
		for (int i = 0; i < g[u].size(); i++)
		{
			int v = g[u][i].v;
			if (dis[s][v] > dis[s][u] + g[u][i].w) {
				dis[s][v] = dis[s][u] + g[u][i].w;
				q.push({ dis[s][v],v });
			}
		}
	}
}

//主程序调用

for (int i = 1; i <= n; i++)Dijkstra(i);

//这样，dis[i][j]就是i到j的最短路径了

询问部分，依然是类似 Floyd 插 \(1 \rightarrow K\) 个点进行松弛操作，其他题解写得很清楚，这里不再赘述。

\(\text{Over.}\)