# OI竞赛中的最短路算法 课前练习： P1111 修复公路 ---------------- 在图论问题中，最短路是一个永恒的主题。当我们超越模板，进入更复杂的应用时，最短路算法就成为了我们解决问题的强大工具。本文档旨在介绍两种核心最短路算法的实现，并深入探讨三种基于它们的高级建模技巧。 ## Part 1: 核心算…

# 思路 采用并查集来动态跟踪桥面的连通性，判断 Rut 最早何时能过河。 # 过程 1. 定义两个虚拟节点 $top$ 和 $bottom$ 分别代表第 $0$ 行和第 $N-1$ 行的陆地。 2. 每处理一个桥面（按时间顺序），就将其添加到并查集中。 3. 若桥面位于第 $1$ 行，则与 $top$ 连通；若位于第…

为了解决这个问题，我们需要计算在给定月初通胀率和 $30$ 个每日变化（可能是百分点或百分比）的情况下，通胀率的最高可能值。关键在于，对于每个每日变化，我们可以选择将其解释为百分点（直接加到当前通胀率上）或百分比（当前通胀率乘以 $1+\Delta\times100\%$ ），以使得最终的通胀率尽可能高。 从月初的通胀…

在讨论《玄关求为啥会有六个点MLE？》回复：

@[Short_person](luogu://user/1499478) 但为啥会MLE呢

```cpp #include #include using namespace std; int n,m,t,ans,sx,sy,fx,fy; bool maze[10][10]; void dfs(int x,int y,int pos){ if(x==fx&&y==fy){ ans++; return; } if…

题目里给出的n的范围是 $10^4$，但实际上需要开到 $10^5$ 才能过最后两个点

在讨论《最后一个点WA玄关求调用数组模拟》回复：

@[aka_ms](luogu://user/1355634)top 不用重置啊，top相当于指针，是实时更新的，为啥要重置啊

在讨论《最后一个点WA玄关求调用数组模拟》回复：

@[aka_ms](luogu://user/1355634)但是没有用啊

在讨论《最后一个点WA玄关求调用数组模拟》回复：

@[aka_ms](luogu://user/1355634)不需要吧，不是直接覆盖原来的吗

```cpp #include #define int unsigned long long using namespace std; int stack[10000001],t,n,num,top=0; void pop(){ top--; } void push(int x){ top++; stack[top]=…

ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็ฏ๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎๎…

这题看起来很复杂，弹珠碰撞时会交换速度和方向，但这一过程其实就等价于“弹珠穿过彼此继续运动”（只是身份互换了）。只要轨迹交叉就一定能发生碰撞，且可通过初始位置安排避免三重碰撞。 所有可能发生碰撞的情况： 1.弹珠的速度不同，无论方向异同必然碰撞。 2.速度相同，方向相反，相遇。 因此，相同速度的弹珠群体中，碰撞数取决于…

$$ \def\arraystretch{1.2} \begin{array}{|c|l|l||c|l|l|} \hline 颜色 & 十六进制 & RGB值 & 颜色 & 十六进制 & RGB值 \\ \hline \color{#52C41A}\text{AC绿} & \text{52C41A} & \text{(…

## 快读 ```cpp int fast_read(){ int k=0,f=1; char c=getchar(); while(c '9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c >n-1); } ``` ## 冒泡排序 ```cpp void bubb…

在讨论《为啥我自己试数和测试数据都对，但一交就WA，求调》回复：

@[fifast](luogu://user/1402877)感谢已关

```cpp #include #include #include #define MAXN 10087 using namespace std; bool cmp(string a,string b){ if(a.size()!=b.size()) return a.size()>b.size(); for(int…

在讨论《第四个点TLE是啥情况，求调》回复：

@[github_eternity_sky](luogu://user/1276392)感谢感谢，已AC+关注

```cpp #include #include using namespace std; int main(){ int a[501],b[501],ans[501]; string A,B; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(ans,0,siz…

在讨论《全部用的已有string函数样例也对为啥全WA》回复：

@[zmq130606](luogu://user/1137662)感谢感谢已改对

```cpp #include using namespace std; int main(){ int cnt=0,i=0,add=100001; string aim,article; getline(cin,aim); //读入 getline(cin,article); int len_aim=aim.size…

```cpp #include #include using namespace std; int main(){ int q,a,b,op; string origin,str; cin>>q>>origin; for(int i=1;i >op; if(op==1){ cin>>str; origin+=str;…

```cpp #include using namespace std; int main(){ int cnt=0,i=0,add=100001; string aim,article; getline(cin,aim); //读入 getline(cin,article); int len_aim=aim.size…

在讨论《过了，但是不理解》回复：

我很想帮你。但奈何你代码我看不懂

这道题的难点主要在于特判，即数据溢出，主要分为两种情况： 第一，答案大于$10^9$； 第二，由于$x$过大，导致直接溢出$int$的正数存储范围（$2^{31}-1$）。 因此，我们只要一步步算出$a^b$并每一步都进行特判即可。 废话少说，直接上代码： ```cpp #include using namespace…

``` #include #include using namespace std; const int mod=10007; int n,m; int a[105]; int time(int x,int y) { int num=1; for(int i=1;i >n>>m; int sum=0; for(int…