本文主要是介绍SP18966 VACATION - Vacation Planning 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目传送门
题意简述
给定一张有向带权图,有 Q Q Q 个请求,每个请求给出点 a i a_i ai, b i b_i bi,费用为 a i a_i ai 经过点 1 → K 1 \rightarrow K 1→K 中的至少一个到达 b i b_i bi 的最小权值和。求出可行的请求数和最小费用和。
分析
有多个询问,很明显是多源最短路,求多源最短路可以用 Floyd,也可以调用 n n 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 → K 1 \rightarrow K 1→K 个点进行松弛操作,其他题解写得很清楚,这里不再赘述。
Over. \text{Over.} Over.
这篇关于SP18966 VACATION - Vacation Planning 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!