【二分查找 图论】P10206 [JOI 2024 Final] 建设工程 2|普及+

本文涉及的基础知识点

C++二分查找 C++图论

[JOI 2024 Final] 建设工程 2

题目描述

JOI 国有

N

N

N 个火车站，编号从

1

1

1 到

N

N

N。另外，JOI 国有

M

M

M 条双向铁路线，编号从

1

1

1 到

M

M

M。铁路线

i

(

1

≤

i

≤

M

)

i\\ (1 \\leq i \\leq M)

i (1≤i≤M) 连接了火车站

A

i

A_{i}

Ai​ 和火车站

B

i

B_{i}

Bi​，从一个站到另一个站需要花费

C

i

C_i

Ci​ 分钟。

你是 JOI 国的部长，决定按照以下方式新建一条铁路线：

选择两个整数

u

,

v

(

1

≤

u

<

v

≤

N

)

u, v\\ (1 \\leq u<v \\leq N)

u,v (1≤u<v≤N)，在火车站

u

u

u 和火车站

v

v

v 之间建设一条双向铁路线，从一个站到另一个站需要花费

L

L

L 分钟。注意，即使已经有一条连接火车站

u

u

u 和火车站

v

v

v 的铁路线也可以建设。

如果你建设这条铁路线后，可以花费不超过

K

K

K 分钟从火车站

S

S

S 到火车站

T

T

T，国王就会高兴。我们不考虑换乘时间和等待时间。

你有

N

(

N

−

1

)

2

\\frac{N(N-1)}{2}

2N(N−1)​ 种选择两个整数

u

,

v

u, v

u,v 的方法，你想知道其中有多少种方法会让国王高兴。

给定火车站和铁路线以及国王的要求的信息，编写一个程序，求出其中有多少种选择整数的方法会让国王高兴。

输入格式

第一行包含两个整数

N

,

M

N,M

N,M。

第一行包含两个整数

S

,

T

,

L

,

K

S,T,L,K

S,T,L,K。

接下来

M

M

M 行，每行包含三个整数

A

i

,

B

i

,

C

i

A_i, B_i, C_i

Ai​,Bi​,Ci​，表示第

i

i

i 条双向铁路线。

输出格式

输出一行一个整数，表示让国王高兴的两个整数的选择方法有多少种。

样例 #1

样例输入 #1

7 8
6 7 1 2
1 2 1
1 6 1
2 3 1
2 4 1
3 5 1
3 7 1
4 5 1
5 6 1

样例输出 #1

4

样例 #2

样例输入 #2

3 2
1 3 1 2
1 2 1
2 3 1

样例输出 #2

3

样例 #3

样例输入 #3

6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000

样例输出 #3

0

样例 #4

样例输入 #4

18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645

样例输出 #4

16

提示

对于所有输入数据，满足：

• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $1\le S<T\le N$
• $1\le L\le 10^9$
• $1\le K\le 10^{15}$
• $1\le A_i<B_i\le N(1\le i\le M)(A_i,B_i)\ne (A_j,B_j)(1\le i<j\le M)$
• $1\le C_i\le 10^9(1\le i\le M)$

详细子任务附加限制及分值如下表所示。

二分+图论

特例：如果在新建铁路之前，K分钟内能从S到T。则直接返回N*(N-1)/2。 性质：方式一

s

→

u

→

v

→

t

s \\rightarrow u \\rightarrow v \\rightarrow t

s→u→v→t和方式二

s

→

v

→

u

→

t

s \\rightarrow v \\rightarrow u \\rightarrow t

s→v→u→t可能两条路径都低于K分钟，也可能一条低于，另一条高于。 排除特例后，性质一的方式一和方式二不会同时存在。反证法：如果同时存在，则一定存在不经过(u,v)或(v,u)的更短路径。 方式一红色。 方式一SV的距离小于等于任意SV的距离。

→

\\rightarrow

→ 方式一SU的距离 小于等于任意UV+VS的距离。用方式一的SU代替方式二UV+VS是不劣解。替换后不经过uv或vu。故存在不经过uv（uv)能够K分钟到达的路径，与特例矛盾。 性质二：排除特例后，u和v相同一定不符合。否则与特例矛盾。 一，单源路径。d1记录s到各点的距离。d2记录各点到t的距离。 二，枚举u ans += upper(d2,K-L-d1[u])-d3.begin()

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;

template<class T = int>
vector<T> Read() {
int n;
scanf("%d", &n);
vector<T> ret(n);
for(int i=0;i < n ;i++) {
cin >> ret[i];
}
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;
}

string ReadChar(int n) {
string str;
char ch;
while (n—) {
do
{
scanf("%c", &ch);
} while (('\\n' == ch));
str += ch;
}
return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {
cin >> pr.first >> pr.second;
}

template<class INDEX_TYPE>
class CBinarySearch
{
public:
CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex, INDEX_TYPE tol = 1) :m_iMin(iMinIndex), m_iMax(iMaxIndex), m_iTol(tol) {}
template<class _Pr>
INDEX_TYPE FindFrist(_Pr pr)
{
auto left = m_iMin – m_iTol;
auto rightInclue = m_iMax;
while (rightInclue – left > m_iTol)
{
const auto mid = left + (rightInclue – left) / 2;
if (pr(mid))
{
rightInclue = mid;
}
else
{
left = mid;
}
}
return rightInclue;
}
template<class _Pr>
INDEX_TYPE FindEnd(_Pr pr)
{
INDEX_TYPE leftInclude = m_iMin;
INDEX_TYPE right = m_iMax + m_iTol;
while (right – leftInclude > m_iTol)
{
const auto mid = leftInclude + (right – leftInclude) / 2;
if (pr(mid))
{
leftInclude = mid;
}
else
{
right = mid;
}
}
return leftInclude;
}
protected:
const INDEX_TYPE m_iMin, m_iMax, m_iTol;
};

class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] – iBase].emplace_back(v[1] – iBase);
if (!bDirect)
{
vNeiBo[v[1] – iBase].emplace_back(v[0] – iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] – iBase].emplace_back(v[1] – iBase, v[2]);
if (!bDirect)
{
vNeiBo[v[1] – iBase].emplace_back(v[0] – iBase, v[2]);
}
}
return vNeiBo;
}
static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
{
vector<vector<int>> neiBo(neiBoMat.size());
for (int i = 0; i < neiBoMat.size(); i++)
{
for (int j = i + 1; j < neiBoMat.size(); j++)
{
if (neiBoMat[i][j])
{
neiBo[i].emplace_back(j);
neiBo[j].emplace_back(i);
}
}
}
return neiBo;
}
};
typedef pair<long long, int> PAIRLLI;
class CHeapDis
{
public:
CHeapDis(int n, long long llEmpty = LLONG_MAX / 10) :m_llEmpty(llEmpty)
{
m_vDis.assign(n, m_llEmpty);
}
void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
{
std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
minHeap.emplace(0, start);
while (minHeap.size())
{
const long long llDist = minHeap.top().first;
const int iCur = minHeap.top().second;
minHeap.pop();
if (m_llEmpty != m_vDis[iCur])
{
continue;
}
m_vDis[iCur] = llDist;
for (const auto& it : vNeiB[iCur])
{
minHeap.emplace(llDist + it.second, it.first);
}
}
}
vector<long long> m_vDis;
const long long m_llEmpty;
};

class Solution {
public:
long long Ans(int N, int S, int T, int L, long long K, vector<vector<int>>& edge) {
S—, T—;
auto neiBo = CNeiBo::Three(N, edge, false, 1);
CHeapDis dis1(N), dis2(N);
dis1.Cal(S, neiBo);
dis2.Cal(T, neiBo);
if (dis1.m_vDis[T] <= K) { return (N – 1LL) * N / 2; }
auto d = dis2.m_vDis;
sort(d.begin(), d.end());
long long ans = 0;
for (auto d1 : dis1.m_vDis) {
ans += upper_bound(d.begin(), d.end(), K – L – d1) – d.begin();
}
return ans;
}
};

int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
int N, M, S, T, L;
long long K;
cin >> N >> M >> S >> T >> L >> K ;
vector<vector<int>> edge(M, vector<int>(3));
for (int i = 0; i < M; i++) {
cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
}
#ifdef _DEBUG
/*printf("N=%d,S=%d,T=%d,L=%d,K=%lldLL,", N, S, T, L, K);
Out(edge, "edge=");*/
#endif
auto res = Solution().Ans(N, S, T, L, K, edge);
cout << res << std::endl;
return 0;
}

单元测试

int N,S,T,L;
long long K;
vector<vector<int>> edge;
TEST_METHOD(TestMethod11)
{
N = 7, S = 6, T = 7, L = 1, K = 2LL, edge = { {1,2,1},{1,6,1},{2,3,1},{2,4,1},{3,5,1},{3,7,1},{4,
5,1},{5,6,1} };
auto res = Solution().Ans(N, S, T, L, K, edge);
AssertEx(4LL, res);
}
TEST_METHOD(TestMethod12)
{
N = 3, S = 1, T = 3, L = 1, K = 2LL, edge = { {1,2,1},{2,3,1} };
auto res = Solution().Ans(N, S, T, L, K, edge);
AssertEx(3LL, res);
}
TEST_METHOD(TestMethod13)
{
N = 6, S = 2, T = 5, L = 1000000000, K = 1LL, edge = { {1,2,1000000000},{2,3,1000000000},{2,4,1000000000},{5,6,1000000000} };
auto res = Solution().Ans(N, S, T, L, K, edge);
AssertEx(0LL, res);
}
TEST_METHOD(TestMethod14)
{
N = 18, S = 4, T = 8, L = 678730772, K = 3000000062LL, edge = { {5,13,805281073},{8,17,80983648},{
3,8,996533440},{10,16,514277428},{2,5,57914340},{6,11,966149890},{8,12,532734310},{2,9,188599710},{2,3,966306014},{12,16,656457780},{16,18,662633078},{1,15,698078877},{2,8,665665772},{2,6,652261981},{14,15,712798281},{7,13,571169114},{13,14
,860543313},{6,7,454251187},{9,14,293590683},{6,14,959532841},{3,11,591245645} };
auto res = Solution().Ans(N, S, T, L, K, edge);
AssertEx(16LL, res);
}

扩展阅读

视频课程

先学简单的课程，请移步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++**实现。