c2c网站的类型,236企业邮箱登录入口,购物网站建设教程,南昌网站建设服务平台给定一个 n 个点 m 条边的有向图#xff0c;图中可能存在重边和自环#xff0c;所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离#xff0c;如果无法从 1 号点走到 n 号点#xff0c;则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整…给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 −1。
数据范围
1≤n≤500, 1≤m≤10^5, 图中涉及边长均不超过10000。
输入样例
3 3
1 2 2
2 3 1
1 3 4输出样例
3
思路
最短路问题可以用dijkstra算法来解决这里是解决各种最短路问题的框架 因为这道题求的是单源最短路且每条路权值都为正数并且边的量级明显大于点1≤n≤500, 1≤m≤10^5是稠密图所以用朴素dijkstra算法解决
朴素dijkstra算法的原理 初始化除了起点之外每个点到起点的距离为无穷大。我们创建一个集合s表示当前已确定最短距离的点对于n个点循环n次每次找到一个不在集合s中的离起点题目中的1号点最近的点然后将它加入集合s并用这个点去更新其他所有点距离。 const int N510;
int n,m;
int g[N][N]; //题目中是稠密图用邻接矩阵写g[1][2]表示从1节点指向2节点的距离
int dist[N]; //从1号点走到每个点的距离最短距离
bool st[N]; //每个点最短路是否已经确定,true为确定
因为是稠密图所以我们用邻接矩阵g[ ][ ]存储边和点的关系。 for(int i0;in;i) //迭代n次每次做两件事1.找到集合外到起点最短距离的点 2.用这个点来更新到其他点的最短距离{int t0; //t表示当前要找的集合外到起点最短距离的点0表示初始化for(int j1;jn;j) //第一轮循环,寻找集合外到起点最短距离的点一开始1号点也是在集合外的所以j从1开始找{//找当前不确定最短距离的点集合外即st为false到起点距离最短的点if(!st[j] (dist[t]dist[j])) //当前点最短路还没被确定并且当前t不是最短的一开始的d[t]是无穷d[1]是0所以1号点就会找到{tj; //换成短的那条路 }}st[t]true; //找到了集合外到起点最短距离的点标记其实就是加入了确定最短距离的集合for(int j1;jn;j) //第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离{dist[j]min(dist[j],dist[t]g[t][j]); //更新1到j这条路的长度从1到t再从t到j的距离与1到j距离比较换成短的那条路} }
dijkst算法的核心代码进行n次循环每次循环找到集合外到起点最短距离的点 然后用这个点来更新到其他点的最短距离。 for(int j1;jn;j) //第一轮循环,寻找集合外到起点最短距离的点一开始1号点也是在集合外的所以j从1开始找{//找当前不确定最短距离的点集合外即st为false到起点距离最短的点if(!st[j] (dist[t]dist[j])) //当前点最短路还没被确定并且当前t不是最短的一开始的d[t]是无穷d[1]是0所以1号点就会找到{tj; //换成短的那条路 }}st[t]true; //找到了集合外到起点最短距离的点标记其实就是加入了确定最短距离的集合
经过第一次循环后我们找到了一个点t将它加入集合s这里每次t初始化为0dist[0]0x3f3f3f3f保证了后面(dist[t]dist[j])找到的是集合s外的点的离起点最近的点因为dist[t]是最大的正无穷多次比较之后dist值最小的点就会加入集合s。 for(int j1;jn;j) //第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离{dist[j]min(dist[j],dist[t]g[t][j]); //更新1到j这条路的长度从1到t再从t到j的距离与1到j距离比较换成短的那条路}
第二个循环用当前找到的点t去更新后面的点到起点的距离方法就是遍历1到n每次看是1号点到j号点的距离大还是1号点到t号点再从t号点到j号点的距离大我们保留短的那条路。 while(m--){int a,b,c;cinabc;g[a][b]min(g[a][b],c); //如果两个点之间有多条边保留最短边因为初始化g为无穷大所以一开始是让g[a][b]c后面如果出现了一样的点就会取其中的最小值}
在主函数中因为题目没有说不存在自边和环所以可能从一个点到另一个点有多条边我们只需要保留其中最短的就好。 补充这里的代码很多处都用到了0x3f是因为这个数字能近似表达正无穷它的值是1061109567是10^9级别并且还能保证无穷大加无穷大仍然不会超限因为0x3f3f3f3f0x3f3f3f3f2122219134这非常大但却没有超过32-bit int的表示范围我们使用memset()是对char操作即一个字节一个字节的操作如果此时初始化的变量为int类型4字节那么此时的变量就会被初始化成四个0x3f即0x3f3f3f3f这个0x是十六进制的意思。 if(dist[n] 0x3f3f3f3f) //当1号点距离到n号点距离为无穷大时即1和n不连通注意这里变成了0x3f3f3f3f{return -1;}
在后面比较的时候注意这个值是0x3f3f3f3f我们只是用memset赋值的时候给每个字节赋值0x3f整个int变量是0x3f3f3f3f。
参考0x3f~0x3f3f3f3f的来龙去脉详解-CSDN博客关于memset函数和赋值0x3f2021-5-5-CSDN博客 示例代码
#includeiostream
#includecstring
#includealgorithm using namespace std;
const int N510;
int n,m;
int g[N][N]; //题目中是稠密图用邻接矩阵写g[1][2]表示从1节点指向2节点的距离
int dist[N]; //从1号点走到每个点的距离最短距离
bool st[N]; //每个点最短路是否已经确定,true为确定int dijkstra()
{memset(dist,0x3f,sizeof(dist)); //初始化时每个点到起点距离为无穷大dist[1]0; //起点到自身的距离为0for(int i0;in;i) //迭代n次每次做两件事1.找到集合外到起点最短距离的点 2.用这个点来更新到其他点的最短距离{int t0; //t表示当前要找的集合外到起点最短距离的点0表示初始化for(int j1;jn;j) //第一轮循环,寻找集合外到起点最短距离的点一开始1号点也是在集合外的所以j从1开始找{//找当前不确定最短距离的点集合外即st为false到起点距离最短的点if(!st[j] (dist[t]dist[j])) //当前点最短路还没被确定并且当前t不是最短的一开始的d[t]是无穷d[1]是0所以1号点就会找到{tj; //换成短的那条路 }}st[t]true; //找到了集合外到起点最短距离的点标记其实就是加入了确定最短距离的集合for(int j1;jn;j) //第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离{dist[j]min(dist[j],dist[t]g[t][j]); //更新1到j这条路的长度从1到t再从t到j的距离与1到j距离比较换成短的那条路} }if(dist[n] 0x3f3f3f3f) //当1号点距离到n号点距离为无穷大时即1和n不连通注意这里变成了0x3f3f3f3f{return -1;}return dist[n]; //返回从1号点走到n号点的距离最短距离
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm; //读入点数和边数memset(g,0x3f,sizeof(g)); //0x3f是无穷大memset按字节赋值一个字节就是0x3fint有四个字节所以是0x3f3f3f3fwhile(m--){int a,b,c;cinabc;g[a][b]min(g[a][b],c); //如果两个点之间有多条边保留最短边因为初始化g为无穷大所以一开始是让g[a][b]c后面如果出现了一样的点就会取其中的最小值}coutdijkstra();return 0;
}
