文章
20
粉丝
224
获赞
56
访问
136.8k
首先,查看答案里的大多数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]存储城...
登录后发布评论
暂无评论,来抢沙发