牛客国庆集训派对Day1___L New Game! —— 最短路

本文主要是介绍牛客国庆集训派对Day1___L New Game! —— 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门

题目大意：

    给出两条平行线和$n$个圆，计算从一条线走到另一条线所消耗的体力。同时，在线上、圆上、园内走不消耗体力，求体力的最小花费。

解题思路：

    一开始没想到是最短路，后来仔细一想，除了最短路也没啥其他的了。将线和圆都想象成一个个点，每个点之间的距离满足以下关系：
$L$_$1$ 到 $L$_$2$ 之间连边权值$\frac{|C_1-C_2|}{\sqrt{A^2+B^2}}$
线$L$与圆$i$之间连边权值$max(0,d(O_i,L_1)-r_i)$
圆$i$与圆$j$之间连边权值 $max(0,d(O_i,O_j)-r_i-r_j)$
最后求最短路即可

代码思路：

    注意要用double，double的绝对值是fabs函数

核心：将线和圆看成一个个点来建图，灵活地运用最短路知识

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const double INF= 1e10+10;
int m, n, vis[N];
double dis[N], mp[N][N];struct node {double x, y, r;
} cc[1005];void init() {for (int i=0; i<=n+1; i++)for (int j=0; j<=n+1; j++) {if (i == j)	mp[i][j] = 0;else mp[i][j] = INF;}
}void creatgraph() {double a, b, c1, c2;scanf("%lf%lf%lf%lf", &a, &b, &c1, &c2);for(int i=1; i<=n; i++)scanf("%lf%lf%lf", &cc[i].x, &cc[i].y, &cc[i].r);mp[0][n+1] = mp[n+1][0] = fabs(c1-c2) / sqrt(a*a+b*b);for(int i=1; i<=n; i++) {double tp = fabs(cc[i].x*a+cc[i].y*b+c1) / sqrt(a*a+b*b) - cc[i].r;if(tp<1e-4) tp=0;mp[0][i] = mp[i][0] = tp;tp = fabs(cc[i].x*a+cc[i].y*b+c2) / sqrt(a*a+b*b) - cc[i].r;if(tp<1e-4) tp=0;mp[n+1][i] = mp[i][n+1] = tp;}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++) {if(i==j) continue;double tp = fabs(cc[i].x-cc[j].x)*fabs(cc[i].x-cc[j].x) + \fabs(cc[i].y-cc[j].y)*fabs(cc[i].y-cc[j].y);tp = sqrt(tp) - cc[i].r - cc[j].r;if(tp <= 1e-4) tp = 0;mp[i][j] = mp[j][i] = tp;}
}void dijkstra(int start) {for (int i=0; i<=n+1; i++)dis[i] = mp[start][i];memset(vis, 0, sizeof(vis));vis[start] = 1;for (int i=1; i<=n; i++) {/*找出离起点最近的点*/double minn = INF;int k = -1;for (int j=0; j<=n+1; j++) {if (!vis[j] && dis[j]<minn) {minn = dis[j];k = j;}}vis[k] = 1;for (int j=0; j<=n+1; j++) {	//松弛操作，找到媒介使得出现新的最短路if (!vis[j] && mp[k][j] < INF)dis[j] = min(dis[j], dis[k] + mp[k][j]);}}
}int main() {scanf("%d", &n);	//n个顶点init();	//初始化地图creatgraph();	//建图dijkstra(0);	//核心迪杰斯特拉算法printf("%.6f", dis[n+1]);	//输出最短路结果
}

这篇关于牛客国庆集训派对Day1___L New Game! —— 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---