|
|
发表于 2021-5-13 18:41:29
|
显示全部楼层
本帖最后由 Hank 于 2021-5-29 10:26 编辑
First：读题
题目
一读题目，哇！最短路径模板题！
一看输入，唉？为啥给我一个表？
一扫输出，呼，这题没那么变态。
一盯范围，艹！这题我谢谢你啊！
那么这题的题目大致如下：
给你一个有向图和一个源点，让你求源点到每个其他点的最短路径
而且存在负边
还要用BF与LXX
（注：BF即Bellman-Ford算法，LXX即链式向前星）
Second:抽象
那接下来咋办呢？
鲁迅曾说：”输入要看懂，就算题目很简单，但输入是必须明白的。“
那就看呗，诶？？？
邻接矩阵？？？
老子要用LXX啊！
但不慌，诶我能转化
Wait，你为嘛用-表示无效啊!
我会跟负数混的！
那怎么办？
Third:scanf
我们都知道scanf是有返回值的，能输就返回1，否则EOF
那......
- long long a;
-
- if(scanf("%lld", &a) == 1)
- {
- aadd(i, j, a);
- }
- else
- {
- continue;
- }
那咋转呢？
那这边建议您仔细看看上面
如果在第i行，第j列看到一个数a
就说明：存在一条从i至j的路径，其权重为a
由于是有向图，加一条就行了
ok，输入完了，注意long long
Fourth:BF
好了，现在就上模板吧：
模板啊，我是不会贴模板的
接着：
本题只差一个东西了：
CODE
- #include<cstring>
- #include<cmath>
- #include<cstdio>
- #include<cstdlib>
- #include<algorithm>
- #include<iomanip>
- #include<string>
- #include<queue>
- #include<iostream>
- using namespace std;
- #define MAX 10
- #define L int
- L n, s;
- L cnt, adj[MAX];
- L f[MAX];
- struct Edge
- {
- L w;
- L to;
- L nxt;
- }edges[10];
- void add(L from, L to, L w)
- {
- edges[cnt].to = to;
- edges[cnt].w = w;
- edges[cnt].to= adj[come];
- adj[from] = cnt;
^(*￣(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吧！- #include<cstring>
- #include<cmath>
- #include<cstdio>
- #include<cstdlib>
- #include<algorithm>
- #include<iomanip>
- #include<string>
- #include<queue>
- #include<iostream>
- using namespace std;
- #define MAX 1011111111
- int n, m, s, t1;
- int cnt, adj[MAX];
- interesting f[MAX];
- struct Point
- {
- int x;
- int y;
- }p11[MAX];
- struct Edge
- {
- int w;
- int to;
- int nxt;
- }edge[10010];
- void add(int from, int to, double w)
- {
- cnt++;
- edges[cnt].to = to;
- edges[cnt].w = from;
- edges[cnt].nxt = adj[from];
- adj[from] = to;
- }
- void init_relax(int s)
- {
- memset(f, 0x3f, sizeof(f));
- f[s] = 0;
- }
- void relax(int from, int to, double w)
- {
- if(f[to] > f[from] + w)
- {
- f[to] = f[from] + w;
- }
- }
- int main()
- {
- cin >> n;
-
- for(int i = 1;i <= n;++i)
- {
- cin >> p[i].x >> p[i].y;
- }
-
- cin >> m;
-
- for(int i = 1;i <= m;++i)
- {
- int u, v;
-
- scanf("%d %d", &u, &v);
-
- 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));
-
-
- aadd(u, v, w);
- aadd(v, u, w);
-
- }
-
- cin >> s >> t;
-
- init_relax(s);
-
- for(int i = 1;i < n;++i)
- {
- for(int j = 1;j <= n;++j)
- {
- for(int k = adj[j];k > 0;k = edges[k].nxt)
- {
- relax(j, edges[k].to, edges[k].w);
- }
- }
- }
-
- printf("%.2lf", f[t]);
-
- return 0;
- }
- #include<cstring>
- #include<cmath>
- #include<cstdio>
- #include<cstdlib>
- #include<algorithm>
- #include<iomanip>
- #include<string>
- #include<queue>
- #include<iostream>
- using namespace std;
- #define MAX 10010
- struct Edge
- {
- int nxt;
- int to;
- double w;
- }edges[MAX];
- struct Point
- {
- int x;
- int y;
- }p[MAX];
- int n, m, s, t;
- int cnt, adj[MAX];
- double f[MAX];
- bool vis[MAX], flag = true;
- void aadd(int from, int to, double w)
- {
- cnt++;
- edges[cnt].to = to;
- edges[cnt].w = w;
- edges[cnt].nxt = adj[from];
- adj[from] = cnt;
- }
- void init_relax(int s)
- {
- memset(f, 0x7f, sizeof(f));
- f[s] = 0;
- }
- void relax(int from, int to, double w)
- {
- if(f[to] > f[from] + w)
- {
- f[to] = f[from] + w;
- }
- }
- int dij(int s)
- {
- init_relax(s);
-
- while(flag)
- {
- flag = false;
- int i = 0;
-
- for(int j = 1;j <= n;++j)
- {
- if(!vis[j])
- {
- if(f[j] < f[i])
- {
- flag = true;
- i = j;
- }
- }
- }
-
- vis[i] = true;
-
- for(int k = adj[i];k;k = edges[k].nxt)
- {
- int l = edges[k].to;
-
- if(!vis[l])
- {
- relax(i, l, edges[k].w);
- }
- }
- }
- }
- int main()
- {
- cin >> n;
-
- for(int i = 1;i <= n;++i)
- {
- cin >> p[i].x >> p[i].y;
- }
-
- cin >> m;
-
- for(int i = 1;i <= m;++i)
- {
- int u, v;
-
- scanf("%d %d", &u, &v);
-
- 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));
-
-
- aadd(u, v, w);
- aadd(v, u, w);
-
- }
-
- cin >> s >> t;
-
- dij(s);
-
- printf("%.2lf", f[t]);
-
- return 0;
- }
不讲了
BDBL
彩蛋
haha
彩蛋上面有彩蛋（提示：我藏起来了，就在上面哦，只有在蓝色中才能发现 ！）
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有帐号？立即注册
x
|
发表于 2021-5-11 18:08:31
置顶卡