最短路之Dijkstra(单源)HDU 2544
2024-09-07 08:00:39
#include <iostream>
using namespace std;
const int Max=;
int map[][];
int d[];
int middist;
bool s[];
void dijkstra(int n,int m)
{
for(int i=;i<=n;i++)
{
d[i]=map[][i];
s[i]=false;
}
int u=;
d[u]=;
s[u]=true;
for(int i=;i<=n;i++)
{
middist=Max;
for(int j=;j<=n;j++)
{
if((!s[j])&&d[j]<middist)
{
u=j;
middist=d[j];
}
}
s[u]=true;
for(int j=;j<=n;j++)
{
if((!s[j])&&map[u][j]<Max)
{
if(d[u]+map[u][j]<d[j])
{
d[j]=d[u]+map[u][j];
}
}
}
}
}
int main()
{
int N,M;
while(cin>>N>>M&&N!=&&M!=)
{
for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
{
map[i][j]=Max;
}
for(int i=;i<=M;i++)
{
int p,q,v;
cin>>p>>q>>v;
map[p][q]=map[q][p]=v;
}
dijkstra(N,M);
cout<<d[N]<<endl;
}
return ;
}
最新文章
- [转]基于display:table的CSS布局
- JavaScript判断字符串的字符长度(中文占两个字符)
- FP—Growth算法
- 深入理解GCD ( 二 )
- Linux入门介绍
- angular 输入框实现自定义验证
- ui-router 父子state共享数据
- 微信小程序button组件样式
- 【转载】PhpStudy修改网站根目录
- HTML条件注释
- 从零开始学 Web 之 JS 高级(二)原型链,原型的继承
- Redux 和 ngrx 创建更佳的 Angular 2
- something about facebook token
- win10下启动zkui
- Beta阶段个人总结
- 【BZOJ4641】基因改造 KMP
- Lack of free swap space on zabbix
- RedHat7配置静态IP
- 【BZOJ3333】排队计划 树状数组+线段树
- C++刷题——2736: 指针练习--输出最大值
热门文章
- css中IE判断语句 if !IE
- BestCoder Round #92 1002 Count the Sheep —— 枚举+技巧
- C语言中的排序算法--冒泡排序,选择排序,希尔排序
- Git基本用法1
- python 文件与文件夹常见操作以及os.walk的用法
- BZOJ_1004_[HNOI2008]Cards_burnside+DP
- vue-cli脚手架搭建Vue.js项目
- JavaScript DOM 编程艺术 --->; JavaScript语法
- android 收集的一些颜色值
- __attribute__((noreturn))的用法