1383最短路径问题

oliver

建帖

Hank

2021/5/13 18:08 已过

Hank

First：读题
题目
一读题目，哇！最短路径模板题！
一看输入，唉？为啥给我一个表？
一扫输出，呼，这题没那么变态。
一盯范围，艹！这题我谢谢你啊！
那么这题的题目大致如下：
给你一个有向图和一个源点，让你求源点到每个其他点的最短路径
而且存在负边
还要用BF与LXX
（注：BF即Bellman-Ford算法，LXX即链式向前星）


Second:抽象
那接下来咋办呢？
鲁迅曾说：”输入要看懂，就算题目很简单，但输入是必须明白的。“

那就看呗，诶？？？
邻接矩阵？？？

老子要用LXX啊！
但不慌，诶我能转化
Wait，你为嘛用-表示无效啊!
我会跟负数混的！
那怎么办？


Third:scanf
我们都知道scanf是有返回值的，能输就返回1，否则EOF
那......

1. long long a;
   
2.                         
   
3.                         if(scanf("%lld", &a) == 1)
   
4.                         {
   
5.                                 aadd(i, j, a);
   
6.                         }
   
7.                         else
   
8.                         {
   
9.                                 continue;
   
10.                         }

复制代码

不就得了
那咋转呢？
那这边建议您仔细看看上面
如果在第i行，第j列看到一个数a
就说明：存在一条从i至j的路径，其权重为a
由于是有向图，加一条就行了
ok，输入完了，注意long long


Fourth:BF
好了，现在就上模板吧：
模板啊，我是不会贴模板的
接着：
本题只差一个东西了：
CODE

1. #include<cstring>
   
2. #include<cmath>
   
3. #include<cstdio>
   
4. #include<cstdlib>
   
5. #include<algorithm>
   
6. #include<iomanip>
   
7. #include<string>
   
8. #include<queue>
   
9. #include<iostream>
   
10. using namespace std;
    
11. 
    
12. #define MAX 10
    
13. #define L int
    
14. 
    
15. L n, s;
    
16. L cnt, adj[MAX];
    
17. L f[MAX];
    
18. 
    
19. struct Edge
    
20. {
    
21.         L w;
    
22.         L to;
    
23.         L nxt;
    
24. }edges[10];
    
25. 
    
26. void add(L from, L to, L w)
    
27. {
    
28.         edges[cnt].to = to;
    
29.         edges[cnt].w = w;
    
30.         edges[cnt].to= adj[come];
    
31.         adj[from] = cnt;

复制代码

FINISH!


^(*￣(oo)￣)^ 接下来是彩蛋：


Fifth:memsetwhy memset double 0x3f is so little?
memset[color=rgba(0, 0, 0, 0.75)] 是按字节填充
double[color=rgba(0, 0, 0, 0.75)] [color=rgba(0, 0, 0, 0.75)]占 8 字节
011111100111111001111110011111100111111001111110011111100111111
这是我们得到的数
而我们看这个数，它是几呢？
利用打印可得为0.747058808803558
so，还是用0x7f吧！

Sixth:SPFA
吗是SPFA?
SPFA = BF + 队列优化
那咋优化？
看这！
然后愉悦地code吧！

1. #include<cstring>
   
2. #include<cmath>
   
3. #include<cstdio>
   
4. #include<cstdlib>
   
5. #include<algorithm>
   
6. #include<iomanip>
   
7. #include<string>
   
8. #include<queue>
   
9. #include<iostream>
   
10. using namespace std;
    
11. 
    
12. #define MAX 1011111111
    
13. 
    
14. int n, m, s, t1;
    
15. int cnt, adj[MAX];
    
16. interesting f[MAX];
    
17. 
    
18. struct Point
    
19. {
    
20.         int x;
    
21.         int y;
    
22. }p11[MAX];
    
23. 
    
24. struct Edge
    
25. {
    
26.         int w;
    
27.         int to;
    
28.         int nxt;
    
29. }edge[10010];
    
30. 
    
31. void add(int from, int to, double w)
    
32. {
    
33.         cnt++;
    
34.         edges[cnt].to = to;
    
35.         edges[cnt].w = from;
    
36.         edges[cnt].nxt = adj[from];
    
37.         adj[from] = to;
    
38. }
    
39. 
    
40. void init_relax(int s)
    
41. {
    
42.         memset(f, 0x3f, sizeof(f));
    
43.         f[s] = 0;
    
44. }
    
45. 
    
46. void relax(int from, int to, double w)
    
47. {
    
48.         if(f[to] > f[from] + w)
    
49.         {
    
50.                 f[to] = f[from] + w;
    
51.         }
    
52. }
    
53. 
    
54. int main()
    
55. {
    
56.         cin >> n;
    
57.        
    
58.         for(int i = 1;i <= n;++i)
    
59.         {
    
60.                 cin >> p[i].x >> p[i].y;
    
61.         }   
    
62.        
    
63.         cin >> m;
    
64.        
    
65.         for(int i = 1;i <= m;++i)
    
66.         {
    
67.                 int u, v;
    
68.                
    
69.                 scanf("%d %d", &u, &v);
    
70.                
    
71.                 double        w = sqrt((p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y));
    
72.                
    
73.                
    
74.                 aadd(u, v, w);
    
75.                 aadd(v, u, w);
    
76.                
    
77.         }
    
78.        
    
79.         cin >> s >> t;
    
80.        
    
81.         init_relax(s);
    
82.        
    
83.     for(int i = 1;i < n;++i)
    
84.     {
    
85.             for(int j = 1;j <= n;++j)
    
86.             {
    
87.                     for(int k = adj[j];k > 0;k = edges[k].nxt)
    
88.                     {
    
89.                             relax(j, edges[k].to, edges[k].w);
    
90.                         }
    
91.                 }
    
92.         }
    
93.        
    
94.     printf("%.2lf", f[t]);
    
95.    
    
96.         return 0;
    
97. }
    

复制代码

Seventh:dijkstra

1. #include<cstring>
   
2. #include<cmath>
   
3. #include<cstdio>
   
4. #include<cstdlib>
   
5. #include<algorithm>
   
6. #include<iomanip>
   
7. #include<string>
   
8. #include<queue>
   
9. #include<iostream>
   
10. using namespace std;
    
11. 
    
12. #define MAX 10010
    
13. 
    
14. struct Edge
    
15. {
    
16.         int nxt;
    
17.         int to;
    
18.         double w;
    
19. }edges[MAX];
    
20. 
    
21. struct Point
    
22. {
    
23.         int x;
    
24.         int y;
    
25. }p[MAX];
    
26. 
    
27. 
    
28. int n, m, s, t;
    
29. int cnt, adj[MAX];
    
30. double f[MAX];
    
31. bool vis[MAX], flag = true;
    
32. 
    
33. void aadd(int from, int to, double w)
    
34. {
    
35.         cnt++;
    
36.         edges[cnt].to = to;
    
37.         edges[cnt].w = w;
    
38.         edges[cnt].nxt = adj[from];
    
39.         adj[from] = cnt;
    
40. }
    
41. 
    
42. void init_relax(int s)
    
43. {
    
44.         memset(f, 0x7f, sizeof(f));
    
45.         f[s] = 0;
    
46. }
    
47. 
    
48. void relax(int from, int to, double w)
    
49. {
    
50.         if(f[to] > f[from] + w)
    
51.         {
    
52.                 f[to] = f[from] + w;
    
53.         }
    
54. }
    
55. 
    
56. int dij(int s)
    
57. {
    
58.         init_relax(s);
    
59.        
    
60.         while(flag)
    
61.         {
    
62.                 flag = false;
    
63.                 int i = 0;
    
64.                
    
65.                 for(int j = 1;j <= n;++j)
    
66.                 {
    
67.                         if(!vis[j])
    
68.                         {
    
69.                                 if(f[j] < f[i])
    
70.                                 {
    
71.                                         flag = true;
    
72.                                         i = j;
    
73.                                 }
    
74.                         }
    
75.                 }
    
76.                
    
77.                 vis[i] = true;
    
78.        
    
79.                 for(int k = adj[i];k;k = edges[k].nxt)
    
80.                 {
    
81.                         int l = edges[k].to;
    
82.                
    
83.                         if(!vis[l])
    
84.                         {
    
85.                                 relax(i, l, edges[k].w);
    
86.                         }
    
87.                 }
    
88.         }
    
89. }
    
90. 
    
91. int main()
    
92. {
    
93.         cin >> n;
    
94.        
    
95.         for(int i = 1;i <= n;++i)
    
96.         {
    
97.                 cin >> p[i].x >> p[i].y;
    
98.         }   
    
99.        
    
100.         cin >> m;
     
101.        
     
102.         for(int i = 1;i <= m;++i)
     
103.         {
     
104.                 int u, v;
     
105.                
     
106.                 scanf("%d %d", &u, &v);
     
107.                
     
108.                 double        w = sqrt((p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y));
     
109.                
     
110.                
     
111.                 aadd(u, v, w);
     
112.                 aadd(v, u, w);
     
113.                
     
114.         }
     
115.        
     
116.         cin >> s >> t;
     
117.        
     
118.         dij(s);
     
119.        
     
120.         printf("%.2lf", f[t]);
     
121.        
     
122.     return 0;
     
123. }
     

复制代码

累了，直接来吧
不讲了
BDBL











彩蛋














                 haha
                                                                                                         
彩蛋上面有彩蛋（提示：我藏起来了，就在上面哦，只有在蓝色中才能发现 ！）               

Hank

2021/5/14 19/48 finish

Hank

已改
00000000000000000000000000000000000

wq

彩蛋是啥？？

李明宇

wq 发表于 2021-5-15 18:40
彩蛋是啥？？

格局小了

wq

你是不是想高人一等:@