y总思路代码

#include 
using namespace std;
int x;
int main(){cin>>x;cout<<(x+5-1)/5;return 0;
}

第二题 AcWing 4871. 最早时刻

一、题目

1、原题链接

4871. 最早时刻

2、题目描述

给定一个 n 个点 m 条边的不含重边和自环的无向图。

点的编号为 1∼n，边的编号为 1∼m。

在 t=0 时刻，你位于 1 号点。

你的任务是尽可能早的抵达 n 号点。

第 i 条边连接点 ai 和点 bi，通过此边需要花费的时间为 ci。

在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。

此外，第 i 个点有 ki 个禁止离开时刻。

在每个点的禁止离开时刻，你无法离开该点前往其它点。

请你计算抵达 n 号点的最早可能时刻。

输入格式

第一行包含两个整数 n,m。

接下来 m 行，其中第 i 行包含三个整数 ai,bi,ci，表示第 i 条边连接点 ai 和 bi，通过此边需要花费的时间为 ci。

接下来 n 行，其中第 i 行首先包含一个整数 ki，表示第 i 个点有 ki 个禁止离开时刻，随后包含 ki 个互不相同的升序排序的整数
tij，表示所有禁止离开时刻。

输出格式

一个整数，表示抵达 n 号点的最早可能时刻。

如果无法抵达 n 号点，则输出 -1。

数据范围

前 4 个测试点满足 2≤n≤4。
所有测试点满足 2≤n≤10⁵，0≤m≤10⁵，1≤ai,bi≤n，ai≠bi，1≤ci≤10⁴，0≤ki≤10⁵，0≤tij<10⁹，所有
ki 相加之和不超过 10⁵。

输入样例1：

4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0

输出样例1：

7

样例1解释
从点 1 到点 4，考虑如下三条路线：

• 在时刻 0 通过第 3 条边离开点 1，并于时刻 8 抵达点 4。
• 在时刻 0 通过第 2 条边离开点 1，并于时刻 3 抵达点 3，由于点 3 在时刻 3,4 禁止离开，所以在时刻 5 通过第 6 条边离开点 3，并于时刻 8 抵达点 4。
• 在时刻 0 通过第 1 条边离开点 1，并于时刻 2 抵达点 2，在时刻 2 通过第 5 条边离开点 2，并于时刻 7 抵达点 4。

最佳方案为第三条路线，抵达点 4 的最早可能时刻为 7。

输入样例2：

3 1
1 2 3
0
1 3
0

输出样例2：

-1

二、解题报告

1、思路分析

思路来源：y总讲解视频
y总yyds

（1）利用Dijkstra算法来确定每个点的最早到达时刻。
（2）由于每个点不是到达后就可立即出发，所以要判断当前时刻是否可以出发，也就是要遍历这个点每个禁止出发的时刻，如果当前时刻正好小于所有的禁止出发时刻，就可以直接走；如果当前时刻正好是禁止出发的时刻就需要等待，直到当前时刻小于所有禁止出发的时刻为止。当前时刻即为该点的最早出发时刻。
（3）按上述过程模拟，求出从1号点到n号点的最早时刻。

2、时间复杂度

时间复杂度为O(mlogn)

3、代码详解

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
const int N=100010,M=2*N;
int h[N],e[M],ne[M],w[M],idx;   //邻接表存储每条无向边
int dist[N];       //存储每个点到1号点的最早时刻
bool st[N];       //存储每个点是否已经确定最早时刻
int n,m;
vector delay[N];      //记录每个点禁止出发的时刻
//邻接表加边
void add(int a,int b,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
//判断当前时刻ver点是否可以直接出发，如果不能出发，将其当前时刻加时到可以出发的时刻
int add_delay(int ver,int distance){//遍历ver点每个禁止出发的时刻for(int i=0;iif(delay[ver][i]==distance) distance++;  //如果当前时刻正好是禁止出发的时刻，则等待时间+1else if(delay[ver][i]>distance) break;   //由于所有禁止出发的时刻是升序排列的，所以当当前时刻小于枚举的禁止出发的时刻，则其一定小于所有后面的禁止出发的时刻，所以直接break，无需继续循环，当当前时刻已经在所有禁止时刻之前，则可以出发，返回出发时刻即可}return distance;
}
//dijkstra算法求最短路
int dijkstra(){memset(dist,0x3f,sizeof dist);priority_queue,greater> heap;dist[1]=0;heap.push({0,1});while(!heap.empty()){PII t=heap.top();heap.pop();//当前最早可出发的点的出发时刻需要加上其到可以出发时刻的等待延迟时间int ver=t.second,distance=add_delay(ver,t.first);if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>distance+w[i]){dist[j]=distance+w[i];heap.push({dist[j],j});}}}if(dist[n]==0x3f3f3f3f) return -3;return dist[n];
}
int main(){cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);   //无向边需存储两个方向}for(int i=1;i<=n;i++){int k;cin>>k;delay[i].resize(k);for(int j=0;jcin>>delay[i][j];}}int t=dijkstra();if(t==-3) cout<<-1;else cout<

#include 
using namespace std;
typedef long long LL;     //每次最短路径的长度最大为500*10^5,而存在500个点所以答案最大可能为500*500*10^5，可能会爆int，所以开成long long
const int N=510;
int d[N][N];   //d[i][j]代表从i到j的最短距离
int ord[N];    //存储删除序列
bool st[N];    //存储每个点是否已经被加入
LL ans[N];     //存储每次最短路的长度
int n;
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>d[i][j];}}for(int i=1;i<=n;i++) cin>>ord[i];//Floyd算法，每次加入一个点，求每次的最短路//倒着枚举，最后一个删除的点即为第一个加入的点for(int u=n;u>=1;u--){int k=ord[u];st[k]=true;      //记录该点为已加入//用该点更新所有点的距离for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//如果i和j都已经加入if(st[i]&&st[j]){ans[u]+=d[i][j];    //则总的最短路距离需要加上其两点间的距离}}}}   for(int i=1;i<=n;i++) cout<