文章

20

粉丝

224

获赞

56

访问

136.8k

头像
先利用Dijkstra或SPFA分别求出求出城市1和城市2到其阵营中其它城市的最短路径,然后对阵营间存在的路径 i 到 j ,求dist(0, i)+D(i, j)+dist(1, j)的最小值
推荐阅读
P1224 北京大学机考题
发布于2022年7月5日 13:05
阅读数 5.5k

首先,查看答案里的大多数AC代码和几篇题解的思路是有问题的,我也是看了好久才发现这个思路是有问题的,比如数据:

3
3
1 2 100
1 3 40
2 3 50
1 2 2

路线应该是1->3->2,花费的最少时间为90,而他们那种方法的路线是直接1->2,花费了100的时间,显然是不正确的,但是也AC了,不过现在数据已加强,应该是通过不了了。

那么我们现在利用其他思路来解决一下,有两种办法。

在此之前,先分析一下题目的意思:

目标是从城市1走到城市2,城市1和2周围是有很多城市的,给你每个城市之间的距离,且这些城市隶属两个阵营,有1和2,走不同阵营的情况只可以出现一次(意思是如果你一开始走了1->2,那之后必须全部在2的阵营走。),让你求从城市1到城市2的最短距离。

不过有一点需要注意,虽然题目中说了“两个城市之间最多有一条道路”,但是不知为啥数据里还是存在重复边的,不知道是不是我理解错题意了,所以需要的时候要对重复边进行处理。

首先是第一种思路:分别求出求出城市1和城市2到其阵营中其它城市的最短路径,然后对阵营间存在的路径 i 到 j ,求dist(0, i)+D(i, j)+dist(1, j)的最小值,代码如下:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 605;
int N, M;

struct Edge {
	int a, b, t;
	Edge(int a, int b, int t):a(a), b(b), t(t) {}
};

vector<Edge> edges;  // 存储每条边
vector<int> G[maxn];  // 存储每个顶点相邻的边在edges的索引
// dist[1]存储城市1到其阵营中其他城市的最短距离,dist[2]存储城...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发