临沂建设局官方网站,基于php网站建设论文,网址搜索ip地址,wordpress宝宝网商城免费模板大家好#xff0c;我们人见人爱、花见花开、车见车爆胎的Peter Pan来啦#xff0c;hia~hia~hia。今天#xff0c;我们今天来学习毒瘤的最短路算法啦。啊这……什么是Dijkstra算法#xff1f;长文警告⚠
正经点啊
手算样例 大家思考一下#xff0c;你在手算样例的时候我们人见人爱、花见花开、车见车爆胎的Peter Pan来啦hia~hia~hia。今天我们今天来学习毒瘤的最短路算法啦。啊这……什么是Dijkstra算法长文警告⚠
正经点啊
手算样例 大家思考一下你在手算样例的时候你是怎么计算的总结一下规律。 Dijkstra
在大多数最短路算法中好像只学了一个Dijkstra算法是最常用、效率最高的一个。他是解决单源多汇问题的单源多汇问题简称SSSP即计算一个起点到其他所有点的最短距离长度。 这题是无权图所以说只是用来练练BFS过会儿Dis算法要用到BFS。
大家练一练十分钟后开放代码。 是不是想偷看代码了 代码
#include bits/stdc.h
using namespace std;
const int N2009;
vectorint to[N];
bool vst[N];
int n,m,d[N];
void bfs(){queueint q;vst[1]1;d[1]0;q.push(1);while(!q.empty()){int u.q.front();q.pop();for(int i0;ito[u].size();i){int vto[u][i];if(vst[v]) continue;vst[v]1;d[v]d[u]1;q.push();}}for(int u1;un;u){if(!vst[u]) cout-1 ;else coutd[u] ;}
}
int main(){cinn.m;for(int i1;im;i){int u,v;cinuv;to[u].push_pack(v);}bfs();来看第二题 BFS
步骤1.从起点s出发用BFS扩展它的邻居节点。把这些点放进一个集合A中并记录这些点到s的距离。2.选择距离s最近的邻居v继续用BFS扩展v的邻居。3.重复步骤2直到所有点都扩展到并计算完毕。那么复杂度是多少呢一般A用优先队列模拟。一共向队列中插入m次取出n次假设每一个点平均有k个邻居那么总复杂度为
代码差不多这样
#include bits/stdc.h
using namespace std;
const long long INF0x3f3f3f3f3f3f3f3fLL;
const int N3e52;
struct edge{int from,to;long long w;edge(int a,int b,long long c){froma;tob;wc;}
};
vectorint e[N];
struct node{int id;long long n_dis;node(int b,long long c){idb,n_disc;}
};
int n,m;
int pre[N];
long long dis[N];
bool done[N];
void dijkstra(){int s1;for(int i1;in;i){dis[i]INF;done[i]false;}dis[s]0;priority_queuenode Q;Q.push(node(s,dis[s]));while(!Q.empty()){node uQ.top();Q.pop();if(done[u.id]) continue;done[u.id]true;for(int i0;ie[u.id].size();i){edge ye[u.id][i];if(done[y.to]) continue;if(dis[y.to]y.wu.n_dis){dis[y.to]y.wu.n_dis;Q.push(node(y.to,dis[y.to]));pre[y.to]u.id;}}}
}
int main(){cinnm;for(int i1;in;i) e[i].clear;while(m--){int u,v,m;cinuvm;e[u].push_back(edge(u,v,m));}dijkstra();for(int i1;in;i){if(dis[i]INF) cout-1;else coutdis[i];}return 0;
}
请同学们进行上机练习练习题目即将公布。
POJ2449 “好男人从来不会让女孩子等待或破坏约会”鸳鸯爸爸说。他轻轻地抚摸着小鸭子的头给它们讲了一个故事。 “雷马古茨王子住在他的王国UDF——自由联合三角洲。有一天他们的邻国派他们乌尤公主去执行外交任务。 “埃雷诺公主给雷马古茨写了一封信告诉他当且仅当王子通过K条最短的路径去见她时她才会来到大厅与UDF进行商业谈判。事实上Uyuw根本不想来“ 对贸易发展和这样一个可爱的女孩感兴趣雷马古茨王子真的被迷住了。他需要你——首相的帮助 详细信息UDF的首都由N个站点组成。大厅编号为S而车站编号为T表示王子的当前位置。M泥泞的侧向连接一些车站。Remmarguts欢迎公主的路径可能包括两次或两次以上的同一车站即使是编号为S或T的车站。
太戈编程1817 中国象棋中的“马”走“日”字我们要研究马在棋盘格里的行走规律。已知棋盘格共有10行9列个格点马的起始位置为第r1行第c1列目标位置是第r2行第c2列。请求出从起点到目标格点的最少步数若无法走到就输出-1。注意马不可以走出棋盘格范围。
太戈编程637 n个星球编号为1,2,3,...,n。星球间可能有直飞火箭往返每条火箭航线的航行时间用邻接矩阵表示如果两个城市间没有直飞用-1表示。求1号星球到各星球最少时间 若无法到达输出-1。n500
太戈编程638 作为武林盟主你希望邀请各门派高手来武林大会切磋武艺。共有n个门派分散在江湖上不同位置编号1到n大会将在1号门派举办。对于第i个门派你打算邀请1个人参会。从任意门派i号到任意不同门派j号有单向通路路费为i*666j*jmod 233。本次武林大会的所有路费由你承担请问总费用至少多少
希望这些对大家有用三连必回
