hdoj 1874 dijkstra

2019-03-01

在做PAT的甲1003,思考DFS和图什么的,时间紧张直接去看柳神(日后上传柳神的C++版本)的订阅,得知是dijkstra,转去用hdoj 1874练手,写了两天,终于调出来了

 

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1874

题目大意:给你点 和 边的数目,接下来输出边的信息(a, b, c表示a和b之间距离为c),最后给你两个数字,表示两点的点信息。让你输出最短路径,没有就-1.

解题思路:dijkstra的思想是贪心,越想越经典。

起始动作就是从出发点开始,把其余所有点到出发点的最近距离存储下,

接下来的动作就是逐渐辐射,

方法是:存储:找到距离出发点最近的点记录下来(从存储的所有点中遍历),这个点就是出发点到这个点的最近距离,

  批量处理:下一次把这个点作为过渡,如果 起点到这个点+这个点到其他某点的距离 < 起点直接到其他某点的距离,就把 起点直接到某点的距离更新为通过过度得到的距离,相当于把所有的更新存储的一下。

再接着执行,直到没有新的点可以加入作为过度为止(注意:每次得出的过度点是上一次得到的,然后上一次得到过度点就是起始点到过度点的最近距离)->(这段话我是脑子里有个这幅图B站女老师(主要学习思路))

 

上段思路我是理解了,可以写出,可以看懂

那么接下来说一下原理,和怎么想到的

上图:

 

 

用到的资料:直接看柳神题解得知是dijkstra,用到的学习资料,B站女老师(主要学习思路),CSDN(主要看看代码思路)

看着不错的界面但是没去看的资料:博客园CSDN1,CSDN2,CSDN3

dijkstra基础题陈列:https://www.cnblogs.com/ACMan/archive/2012/07/23/2605673.html

动态演示:我反应慢,思维也慢,没跟上https://www.cnblogs.com/ly199553/p/5547808.html

卿学姐代码风格:https://www.bilibili.com/video/av4224493/?spm_id_from=333.788.videocard.3

 

容易WA的地方

1.重边的处理
2.起点与终点相同的情况

参考:http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=36571&messageid=1&deep=0

 

 

 

代码:

  1 /***************************************
  2 * About:    hdoj 1874(Dijkstra)
  3 * Author:   GerJCS
  4 * B log:
  5 From: 19/2/27
  6 ***************************************/
  7 
  8 /*
  9 
 10 思路
 11 */
 12 
 13 //#include<bits/stdc++.h>
 14 #include<cstdio>
 15 #include<cstring>
 16 using namespace std;
 17 #define INF 999999
 18 int e[250][250];
 19 int visit[1050];
 20 int dis[250];
 21 int m, n;
 22 int a, b, c;
 23 int start, end;
 24 void init1()
 25 {
 26     for(int i = 0; i < m; i ++)
 27         for(int j = 0; j < m; j ++){
 28             if(i == j)
 29                 e[i][j] = 0;
 30             else{
 31                 e[i][j] = INF;
 32                 e[j][i] = INF;
 33             }
 34         }
 35 }
 36 void init2()
 37 {
 38     for(int i = 0; i < m; i ++)
 39         visit[i] = 0;
 40     visit[start] = 1;
 41     for(int i = 0; i < m; i ++)
 42         dis[i] = e[start][i];
 43 }
 44 //int dijkstra()
 45 void dijkstra()
 46 {
 47     int u = -1;
 48     int min;
 49     for(int i = 0; i < m - 1; i ++)
 50     {
 51         min = INF;
 52         for(int j = 0; j < m; j ++)
 53         {
 54             if(!visit[j] && min > dis[j])
 55             {
 56                 min = dis[j];
 57                 u = j;
 58             }
 59         }
 60 //        if(u == -1)
 61 //            return -1;
 62 //        if(u == end)
 63 //            return dis[u];
 64         visit[u] = 1;
 65         for(int k = 0; k < m; k ++)
 66             if(!visit[k] && dis[k] > dis[u] + e[u][k])
 67                 dis[k] = dis[u] + e[u][k];
 68     }
 69 //    return -1;
 70 }
 71 int main()
 72 {
 73 //    freopen("C:/Users/GerJCS岛/Desktop/ddd.txt","r",stdin);
 74 //    freopen("C:/Users/GerJCS岛/Desktop/out2.txt","w",stdout);
 75     while(scanf("%d%d", &m, &n) != EOF)
 76     {
 77         memset(e, 0, sizeof(e));
 78         memset(visit, 0, sizeof(visit));
 79         memset(dis, 0, sizeof(dis));
 80         init1();
 81         for(int i = 0; i < n; i ++)
 82         {
 83             scanf("%d%d%d", &a, &b, &c);
 84 //            e[a][b] = c;
 85 //            e[b][a] = c;
 86             if(c < e[a][b]){
 87                 e[a][b] = c;
 88                 e[b][a] = c;
 89             }
 90         }
 91 
 92         scanf("%d%d", &start, &end);
 93         init2();
 94         dijkstra();
 95 //        printf("%d\n", dijkstra()); 
 96         if(dis[end] == INF)
 97             printf("-1\n");
 98         else
 99             printf("%d\n", dis[end]);
100     }
101 }
102 
103 
104 
105 //3 4
106 //0 1 1
107 //0 2 1
108 //1 2 1
109 //0 2 9
110 //0 2

 

------------------------------------------------------------------------------待更新!-----------------------------------------------------------------------------

 

工具:http://tool.chinaz.com/Tools/textencrypt.aspx

密码:139*****136

加密后文字:

U2FsdGVkX19wgyNcTGQ7XiAr3GegDzjioUFtqCDiTpEjH3U8PCn0MGej0sbXbpmJ
/ek4/l8Di9oGOAFRHkQNZM4aRC474gAVDVi2L4FYs4rLjuxbYGh4ZydVxcVBXQPc
muey88tUTJJ0JpIUI7BR3teM9rtWec4JEWB/1H2khm6j+T+mm2qv+DpUcjZCWpoG
tRgFhQEnHfORwj95LI98+zPWjTC4ggmDYr21JleIbFaZ6CmbsiX/XtxkOAUZrz6q
8xwj+BRUyCxwjl0aR+98SgtY/HRw1B1hFMYk/Lm5Q41Fk+EXSsFvHI9UI3l4HNZe
g/LcjheiRBV3N5o4AH9qnLJIFhO0zFzzk9x0bM5/svtUEJVXpRqNjimx+vtuBSCi
d6oJbvI3dqVx7b7ukUOe0X6r0cAa5OFbbtR9+qNSBMiT6GKDb0riT8YP9c2PcOv4
phEJ83vWJtfTAf+g+upsGZtM3dT/yTRMdYwyVxkWvtoRl53PYm6/xOvgAuUOKWAF
thfH+nE3SHskAC/hOIVFue7R8bmFI8Ld/vG04bTTwmgM1rh+BwDEpCDuaExlUFI/
oanl8bCb66gMP/20XhHUzUZv6JsF6HmQPBfIw4ikcYboCk4lTLlu3oQYi7qy1hSs
km9uuBYFBc3ygaxjW//zTWYW5HOKPCp05p/q+/wYvEYC1OyChrocHpqhD7dB4FSR
oPWUvTvNS5ym4QsXnzzXLZ9CoYAic8iWWKMM/CPC5BOaolwdvlGM9zLDdoTqxqJ5
JiYndAf47DMXOxVUle9VvKv1MvL7Xk5qajPHVn9p5mHkdQicb0W64JLGA3DeZIQ/
f8i/KiKFwJxIs2qxjfj9DuF/P8kSbIJmE+ayJ5Yiml38bY6d+KDsQf0wNsc527Fr
vKouoogXgmINlHuly5Zy+iob6y8DbFzOgP2u9kow87zCEgSntpr9BGhP6wNyp5xp
LVkkfz5rXKrAJMIFCmJhMht8E//LYQmdJkTUsUqbF3MZc40HfQPE4LUfdRUBNTkj
O8hE6hLDNXQgXgO26Mf441T2FRKQYPH/3DYYlnRgly57kwBOu2wjpKC6WsE4JJWJ
683mzF/dTZxaNE+c6uAdbNvKUiETr4dlWXktIUWZO+Zo2SHVGvd9/lR0x354Wf/B
/YxZwv8mJxAI4qCSQVHwZEQlSRAHTpuqPxqZPd2dpB9YiB5+uEw6li4MEgESYsVk
YQJvbEDHBTH6R9RitJ79GBWOpPDs5HbBK5B1BWSgbLdRxvnWeV/DV9dnnA6smEDw
qBP2tmfTg/qTvaHYKj3xQkqGV3xFteiET1NRGlt+zhxc0axf3lMfdxecLlAy6zEU
Nv4MKTufILpY0dp1iy/uQLTkRLj8uCoEbK1e+CDNSNPS39rZwhfJjTol5CracvHs
RMDONEfHbEyxyoBmDgJUXjnUALTncc+4trIigiWOX0F/bz5lFU7Y/MCftzo+xpvV
9ChBNReSnry9/+m0UXEh124X362L+dqCb5iK+Nx1LE2iIKFs7GmT2m9u3pLFu1YR
On9UFXZiN15zsCgzU4+X2dLvc1CSlrOZAt2AUpgjdZ/4iDJqom3CDoBQNr0/I9Vt
7fUqnlXliPbe51uyJqX8fsbd27ty5vnG8mrdz+m6/mc=

 

人权!资本!圈子!平台!