【图论 次短路】P1491 集合位置|省选-

本文涉及知识点

C++图论 次短路

P1491 集合位置

题目描述

每次有大的活动，大家都要在一起“聚一聚”，不管是去好乐迪，还是避风塘，或者汤姆熊，大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放，还记得草草的投篮技艺是如此的高超，还记得狗狗的枪法永远是 S ……还有不能忘了，胖子的歌声永远是让我们惊叫的！！

今天是野猫的生日，所以想到这些也正常，只是因为是上学日，没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。

但是每次集合的时候都会出现问题！野猫是公认的“路盲”，野猫自己心里也很清楚，每次都提前出门，但还是经常迟到，这点让大家很是无奈。后来，野猫在每次出门前，都会向花儿咨询一下路径，根据已知的路径中，总算能按时到了。

现在提出这样的一个问题：给出 $n$ 个点的坐标，其中第一个为野猫的出发位置，最后一个为大家的集合位置，并给出哪些位置点是相连的。野猫从出发点到达集合点，总会挑一条最近的路走，如果野猫没找到最近的路，他就会走第二近的路。请帮野猫求一下这条第二最短路径长度。

特别地，选取的第二短路径不会重复经过同一个点，即使可能重复走过同一个点多次路程会更短。

输入格式

第一行是两个整数 $n(1\le n\le 200)$ 和 $m(1\le m\le 10000)$，表示一共有 $n$ 个点和 $m$ 条路，以下 $n$ 行每行两个数 x i x_i xi​， y i y_i yi​， (−500≤ x i , y i ≤500), (-500 \\le x_i,y_i \\le 500), (−500≤xi​,yi​≤500), 代表第 $i$ 个点的坐标，再往下的 $m$ 行每行两个整数 p j p_j pj​， q j ,(1≤ p j , q j ≤n) q_j,(1 \\le p_j,q_j \\le n) qj​,(1≤pj​,qj​≤n)，表示两个点之间有一条路，数据没有重边，可能有自环。

输出格式

只有一行包含一个数，为第二最短路线的距离（保留两位小数），如果存在多条第一短路径，则答案就是第一最短路径的长度；如果不存在第二最短路径，输出 -1。

输入输出样例 #1

输入 #1

3 30 01 10 21 21 32 3

输出 #1

2.83

单源最短路

性质一：次短路不会包括最短路所有边。
一，先用朴素迪氏求出单源最短路，及经过的边。由于没有环，故边数不超过N。
二，依次删除最短路各边，重新求最短路，最小值就是答案。

代码

核心代码

#include #include #include #include#include#include#include#include#include#include#include#include #include#include#include #include #include#include#include#include using namespace std;template<class T1, class T2>std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;}template<class T1, class T2, class T3 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;}template<class T1, class T2, class T3, class T4 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;}template<class T1, class T2, class T3, class T4,class T5 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);return in;}template<class T1, class T2, class T3, class T4, class T5,class T6 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5,T6>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>get<5>(t);return in;}template<class T = int>vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}template<class T = int>vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if (\'\\n\' == cin.get()) { break; }}return ret;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}template<int N = 1\'000\'000>class COutBuff{public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = \'-\', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char puffer[N], * m_p;};template<int N = 1\'000\'000>class CInBuff{public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == \'-\');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == \'-\');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;};template<class T = long long, class T1 = int>class CN2DisEx{public:CN2DisEx(int iSize, T tDef = LLONG_MAX / 2) :m_iSize(iSize), m_tDef(tDef), DIS(m_vDis), PRE(m_vPre){}void Cal(int start, const vector<vector<pair<int, T1>>>& vNeiB){m_vDis.assign(m_iSize, m_tDef);m_vPre.assign(m_iSize, -1);vector<bool> hasDo(m_iSize);auto AddNode = [&](int iNode){auto llPreDis = m_vDis[iNode];for (const auto& [next, w] : vNeiB[iNode]){if (llPreDis + w < m_vDis[next]){m_vDis[next] = llPreDis + w;m_vPre[next] = iNode;}}auto llMinDis = m_tDef;int iMinIndex = -1;for (int i = 0; i < m_vDis.size(); i++){if (hasDo[i]){continue;}if (m_vDis[i] < llMinDis){iMinIndex = i;llMinDis = m_vDis[i];}}if (-1 != iMinIndex) { hasDo[iMinIndex] = true; }return iMinIndex;};int next = start;m_vDis[start] = 0;while (-1 != (next = AddNode(next)));}const vector<T>& DIS;const vector<int>& PRE;const T m_tDef;private:const int m_iSize;vector<T> m_vDis;//各点到起点的最短距离vector<int> m_vPre;//最短路径的前一点};class Solution {public:double Ans(vector<pair<int,int>>& rc, vector<pair<int, int>>& edge2) {const int N = rc.size();;vector<tuple<int, int, double>> edge;for (auto [u, v] : edge2) {u--, v--;const auto& [x1, y1] = rc[u];const auto& [x2, y2] = rc[v];double w = (1.0 * x1 - x2) * (x1 - x2) + (1.0 * y1 - y2) * (y1 - y2);w = sqrt(w);edge.emplace_back(min(u, v),max(u,v), w);}auto NeiBo = [&](int uEx, int vEx) {if (uEx > vEx) { swap(uEx, vEx); }vector<vector<pair<int, double>>> neiBo(N);for (const auto& [u, v, w] : edge) {if ((u == uEx) && (v == vEx)) { continue; }neiBo[u].emplace_back(v, w);neiBo[v].emplace_back(u, w);}return neiBo;};CN2DisEx<double,double> dis(N, 1e308 / 2);auto neiBo = NeiBo(-1, -1);dis.Cal(0, neiBo);if (dis.m_tDef == dis.DIS.back()) { return -1; }double ans = dis.m_tDef;for (int u = N - 1; ;) {const int v = dis.PRE[u];if (-1 == v) { break; }CN2DisEx<double, double> dis1(N, 1e308 / 2);auto neiBo1 = NeiBo(u, v);dis1.Cal(0,neiBo1);ans = min(ans, dis1.DIS.back());u = v;}return (dis.m_tDef == ans) ? -1: ans;}};int main() {#ifdef _DEBUGfreopen(\"a.in\", \"r\", stdin);#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);int N, M;cin >> N >> M;auto rc = Read<pair<int,int>>(N);auto edge2 = Read<pair<int, int>>(M);#ifdef _DEBUG//printf(\"N=%d,S=%d,P=%d\", N, S, P);Out(rc, \"rc=\");Out(edge2, \",edge2=\");//Out(fun, \",fun=\");//Out(que, \",que=\");#endif // DEBUGauto res = Solution().Ans(rc, edge2);printf(\"%.2lf\", res);return 0;}

单元测试

vector<pair<int, int>> rc,edge2 ;TEST_METHOD(TestMethod11){rc = { {0,0},{1,1},{0,2} }, edge2 = { {1,2},{1,3},{2,3} };auto res = Solution().Ans(rc, edge2);AssertEx(2.83, res,0.01);}

扩展阅读

我想对大家说的话 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 如果程序是一条龙，那算法就是他的是睛 失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。