本文共 8025 字，大约阅读时间需要 26 分钟。
还记得之前数据结构老师说过，这是个荷兰人的名字。。。所以你无论咋的你找不到这个人的英文名= -。。。。
最近真的好咸鱼啊= =7天A了一个题还是签到题的A= -
还有就是...感觉忘得太快了.....
懵懵懂懂的记得的话也会自己写着写着又错代码打的太少吧....
嗯....那可以加一个日常复习业务= =
https://blog.csdn.net/zhembrace/article/details/72512858这里说...
练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打//有趣,可以试一试出来. ..
(〃'▽'〃)反正..熟能生巧 没错的
https://blog.csdn.net/selinafelton/article/details/52157412
**************************************
要注意什么呢?
这个最短路其实也就是一个简化过了的bfs... 首先,把边读入的时候,因为这个题是无向图,所以 输入的a1,a2,v,那么,a1这里面存储一个:a1到a2(出度),a1到a2是v(权值) 同样a2到a1也是这样,所以存储两次 这样遍历完之后,对于所有的边,就是把一条边的出度都保存起来 比如a1,那么也就是从a1出发,有三条出去的边,你可以这样这样从a1往下走,他们的权值也都一并保存了 用vector 存的话,vector是个动态数组,所以使用起来很方便,前面的a1是个下表,a1.size里面的他的出度,可以有很多 又因为,要存两个呀,所以用node存那么一下 写起来就是,vector<node> e;//cun bian e[a1].push_back(node(a2,v)); (...这个题似乎不太对= =(划掉) 这样就可以完成初步了-都存了起来,fine (其实和之前...bfs实现有向无环图是一个思想= -.. 多看看吧,忘的好快=-=(是不常用 加上不够熟吧)) 存起来之后,就要找了,借用vis数组和dis数组会更加方便一点 而且最短路这边是最短的,所以开始那边 要是在优先队列里进来.....进来被优化过了就fine 和普通的bfs不同的就是每次都选取最优的那个边,所以使用了优先队列实现,其他的都差不多- - 【注意1】看上面 【注意2】用优先队列改变排序- - 在结构体里面就要声明，记一下、、 下面那个不完整的代码里也有相关信息 然后就是常规操作了 最最开始vis和dis都要清空，dis设置成最大的inf 队列也要清空 把起点压进去 dist[start] = 0 ;（自己到自己是0咯，其实也根本用不到这个用.. 但是之后要用它进行加法运算和比较,所以） que.push(qnode(start , 0)) ; (把第一个压进去...第一个的dis等于0 ,就是预设的dis是0 ,然后关键是获取了start啊,获取了start就可以找到start的一大堆出度,每个出度都跑跑跑,,,,,) 然后还是常规操作... int u = temp.next ; if(vis[u]) continue ; vis[u] = true ; //但是u是什么呢? 【】 想了一下...似乎,因为,这是一个连通的图, 你想要实现，似乎只能从起点开始走吧... 这样的话,想要存储的其实不多诶,除非有一条边直接相连,其他的完全都是不可达的..不可达那担心个鸡毛 存在e里面的东西其实不用怕:为什么不用怕呢,因为只是当你a1连接到的时候,a1里面的一堆a2是可更新的,代表从起点开始,从起点开始往后扒拉...扒拉到a1的时候有a2和其他一些很多选项,后面那些a2是顺便更新一下的,当你a1成为正房的时候,因为每一次都是最短的进去的,所以a1是直接确定下来的 其实按照这个压法,这也仅仅只是next,和到达next的value,(叫next可能会引起误解= -) 同时也相当于的哦,它们并不是被直接确定的 而是,一直在被更新,每找到一个新的点,就把它的家族全部都更新过一遍 (下面zj的代码有个优化...如果比存着的dis还要长的话,就无所谓啦,continue掉,fine) 直到这个点已经失去了使用价值,那么在这样一个队列里面,排好顺序并且有优先级,它被推上了历史的舞台 前面比他好的都死掉了,所以因此就没有比他更好的了 他就会把他的家族也更新一遍,然后死去 ....关键把edge里面的那么多 边取出来,然后比较一下啊= - 【准备工作】(划重点) 1.优先队列 2.vis数组(是否访问,bool) 3.struct里面x和他的dis(暂时的) 4.dist数组(用于记录最后确定下来了来的距离) 5.vector(用于记录边的出度) (其中queue可以不用下标) (其中struct也可以不用) 同理,清空的时候需要对vis进行memset,dist进行inf,优先队列进行pop,vector进行clear(分别) 【bfs开始前的准备工作】 除了清空之外 1.dis[x]=0(自己到自己是0) 2.push进node(x,0) 3.pop之后记录为u和temp 4.vis[u]=true
**************************************
#include#include #include #include #include using namespace std ;const int INF = 0x3f3f3f3f ;const int MAX = 10010 ;struct qnode{ int v ; int c ; qnode(int _v = 0 ,int _c = 0) : v(_v) , c(_c) {} bool operator <(const qnode &r) const { return c > r.c ; }};struct Edge{ int v , cost ; Edge(int _v=0 , int _cost = 0):v(_v) ,cost(_cost) {}};vector E[MAX];bool vis[MAX] ;int dist[MAX] ;void Dijkstra(int n , int start){ memset(vis , false , sizeof(vis)) ; for(int i = 1 ; i <= n ; i ++) dist[i] = INF ; priority_queue que ; while(!que.empty()) que.pop() ; dist[start] = 0 ; que.push(qnode(start , 0)) ; qnode temp ; while(!que.empty()) { temp = que.top() ; que.pop() ; int u = temp.v ; if(vis[u]) continue ; vis[u] = true ; for(int i = 0 ; i < E[u].size() ; i++) { int v = E[temp.v][i].v ; int cost = E[u][i].cost ; if(!vis[v]&&dist[v]>dist[u]+cost) { dist[v] = dist[u] + cost ; que.push(qnode(v,dist[v])) ; } } }}void addedge(int u , int v , int w){ E[u].push_back(Edge(v , w)) ;}int A[MAX] , B[MAX] , C[MAX] ;int main(){ int n,m; int T; while(~scanf("%d%d",&n,&m) , n+m) { for(int i=0;i
然后,下面是子自己打的一个和zj的原代码....
***********ac one*****************\
//yuyuleixianliu ..... ..#include#include #include using namespace std;struct node { int next; int dis; bool operator< (const node &p)const { return dis > p.dis; } node(int _next=0,int _dis=0):next(_next),dis(_dis){}}h[105];vector e[105];//记录边的地方....priority_queue q;bool vis[10005];//边int dist[10005];const int INF = 0x3f3f3f3f;void dij(int x, int n) { memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) dist[i] = INF; while (!q.empty()) q.pop(); dist[x] = 0;//...自己到自己是0 没错吧 q.push(node(x, 0));//吧自己也加进去..没错吧 while (!q.empty()){ node temp = q.top(); q.pop(); int u = temp.next; if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++){ int v = e[temp.next][i].next; int cost = e[u][i].dis; if (!vis[v] && dist[v] > dist[u] + cost){ dist[v] = dist[u] + cost; q.push(node(v, dist[v])); } } }}int main() { int n, m; while (cin >> n >> m) { if (m == 0 && n == 0)break; int a1,a2,v; for (int i = 0; i < n; i++)e[i].clear(); for (int i = 0; i < m; i++){ cin >> a1 >> a2 >> v; e[a1].push_back(node(a2, v));//出度和值.. e[a2].push_back(node(a1, v)); } dij(1, n); long long ans = dist[n]; cout << ans << endl; } return 0;}
容易错的地方还有:
忘记vis数组的清空了
还有....清空/初始化的时候
边那里用到的是1到n的
所以万一没清空的话就是默认的最小值
因为边存储的方式是不一样的 是1到n 从0开始就会有偏差 错了一次
代码地址https://vjudge.net/contest/220695#status//C/0/
总觉得自己打的错了...
然后是晚上自己打的(可能会错.没交)
#include#include #include using namespace std;struct node { int x; int dis; bool operator<(const node &a)const{ //本来 1<2的 return dis > a.dis; //想1>2 1优先极更高所以先出去 } node(int _t,int _dist):x(_t),dis(_dist){}};vector e[10005];int dist[10005];bool vis[10005];#define inf 9999;priority_queue q;void dij(int x, int n) { //先清空... //全都砍熟了之后里面真的没啥了... memset(vis, false, sizeof(vis)); while (!q.empty())q.pop(); for (int i = 1; i <= n; i++) dist[i] = inf; dist[x] = 0; q.push(node(x, 0)); while (!q.empty()) { node temp = q.top(); q.pop(); int u = temp.x;//也不复杂,只是给提取出来了而已 //【这里需要写vis if (vis[u])continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int cost = e[u][i].dis; int v = e[u][i].x;//....这些是它能见到的边呀 //为啥要这样呢...因为e[i]有很多的嘛 //是 u i... 因为 你先找到他是第五个 然后第五个这里面 存了2个边 边就是size //i在后面啊= - // if (!vis[v]&& if(dist[v] > cost +dist[u])/// temp.dis) {//更新和压入. dist[v] = cost + dist[u];// temp.dis; q.push(node(v,dist[v])); } } }}int main() { int m, n; while (cin >> n>> m) { if (m == 0 && n == 0)break; int a1, a2, v; for (int i = 0; i < m; i++) e[i].clear(); for (int i = 0; i < m; i++) { cin >> a1 >> a2 >> v; e[a1].push_back(node(a2, v)); e[a2].push_back(node(a1, v)); } //读完边了之后就完了 dij(1, n); cout << dist[n] << endl; } return 0;}
(不完整)
#include#include #include using namespace std;struct edge { int to, dist;};vector g[500];//每个结点的边struct node { int id, dist;//标号和距离 bool operator < (const node &p) const { dist > p.dist; //它的大于也是大于的意思,小于也重载成了大于的意思 //没重载之前,如果是1<2 2 first(2先出去,因为它优先级高) //define 1>2 then 1 first/小的先出去 //重载了node的小于号 //这样优先队列里面,最先出去的就是最小的了,符合我们想达到的效果 }};/*【多傻啊！！！其实这只是一个变相的bfs而已!!!】 以后不要看这种乱七八糟网上写的题解了..(我怎么有种想撒狗粮的冲动......)【那个里面进行找边的时候，排序吗？排序要一个一个找？【直接优先队列！！！】【每次都找到最小的那个边，访问过之后就finecontinue那个是简化操作的，1+1<2了 那还要2干什么 可以简化很多的*/int vis[105];int main() { priority_queue q; //读入边,把第一个塞进去,其他的存起来(读的时候注意一下,@之前有向无环图的边的存储方法) while (!q.empty()) { node u = q.top(); q.pop(); //排序过的top (小的先出 if (vis[u.id] < u.dist) continue;//其实是dis距离... for (int i = 0; i < g[u.id].size(); i++) { edge e = g[u.id][i];//还是参考之前有向无环图的边的存储方法,把几个出度都考虑一遍 //是这个意思吧,如果读到的边加上之前的,比存储过的还小的话 //就进行两部操作:1更新,2push进去以便下一步查找 if (u.dist + e.dist < vis[e.to]) { q.push(node{ e.to,vis[e.to] = u.dist + e.dist }); } } } //最短路和dijskra....只是个bfs而已啦 return 0;
4.8 错在哪儿= -
1. 初始化的时候=0
2.inf define的不够大? 而且 不是define 直接const int也可以 0x3f3f3f3f..... 0x3f3f3f3f 3.for (int i = 1; i <= n; i++) dist[i] = INF; 这里是n因为是边 (是1到n,注意一下) 4.更新的时候 if (dist[v] > cost + dist[u])/// temp.dis) {//更新和压入. vist[v] = cost + dist[u];// temp.dis; q.push(node(v, dist[v])); } 是把你这个节点存着的本来的v,和cost加上之前的u (事实证明,一样的...因为temp.dis也是优化过的,不再动的dist) 5.还有就是结果 是long long (根本没有用,错不在这儿) 6.if (!vis[v] && dist[v] > dist[u] + cost) 前面访问标记是累赘,也用不到这个 ............... 我觉得上面这些都没有用.... 关键是我把清空e的时候e应该是和点有关的n,写成m了... ...fine 所以初始化的时候有两个要注意的然后就是define inf是0x3f3f3f3f
(就是,我手上打的那个的确是错的= -)