最短路径:初涉Dijkstra算法
2024-10-08 09:15:03
模板题目:https://www.luogu.com.cn/problem/P1339
我的代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f;
using namespace std;
int n,m,s,t;
int w[][];//初始化为INF
int d[];
int vis[]; int main()
{
freopen("input.txt","r",stdin);
cin>>n>>m>>s>>t;
memset(vis,,sizeof(vis));
for(int i=;i<n;i++) d[i]=(i==s-)?:INF;//0赋值给起点
for(int i=;i<n;i++) for(int k=;k<n;k++) w[i][k]=INF;
//
int a,b,p;
for(int i=;i<m;i++)
{
cin>>a>>b>>p;
a--;b--;//由于输入文件里是[1,n],而模板中是[0,n)所以找了好久才发现
if(w[a][b]>p){w[b][a]=w[a][b]=p;}
}
//
for(int i=;i<n;i++)
{
int x,m=INF;
for(int y=;y<n;y++)if(!vis[y]&&d[y]<=m)m=d[x=y];
vis[x]=;
for(int y=;y<n;y++)d[y]=min(d[y],d[x]+w[x][y]);
}
printf("%d\n",d[t-]);
return ;
}
其他博主的文章:
https://blog.csdn.net/m0_38004914/article/details/81209125
https://blog.csdn.net/kprogram/article/details/81225176
OK
最新文章
- Odoo 二次开发教程(二)-模块的基础构建
- String类型传值以及对象传值
- Appium移动自动化测试之安装Appium
- HBase Java简单示例
- Java虚拟机 - 内存模型
- MOOCULUS微积分-2: 数列与级数学习笔记 Review and Final
- 剑指offer习题集2
- java14-9 Doteformat的练习
- Chart控件的多种使用方法
- MySQL INSERT DELAYED
- jquery之分页插件smartpaginator
- 一个高级PHP工程师所应该具备的
- Android再学习-20141018-布局-进度条
- javamail发送邮件的简单实例(转)
- TensorFlow与主流深度学习框架对比
- HTML5新增的标签及使用
- ZOJ3774 Power of Fibonacci 斐波那契、二项式定理
- 1259 整数划分 V2
- jQuery中的extend()方法
- yii2 配合bootstrap添加一个气泡