用数据结构输入格式:第一行是两个以空格符分隔的整数n和m;接下来的第二行到第m+1行,每行包含4个以空格分开的元素x,y,w和d来描述一条道路,其中x和y是一条长度为w的道路相连的两个农场的编号,d是字符N.E.S.或W,表示从x到y的道路的方向。输出格式:给出最远的一对农场之间距离的整数。
时间: 2024-01-21 22:16:17 浏览: 129
这道题可以考虑使用图论中的最短路算法,例如Dijkstra算法或者Floyd算法。下面是一个使用Dijkstra算法的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge {
int to; // 目标农场编号
int dist; // 道路长度
char dir; // 道路方向
};
vector<Edge> edges[100005]; // 存储边信息的邻接表
int dis[100005]; // 存储起点到各个农场的最短距离
void dijkstra(int from) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
memset(dis, INF, sizeof(dis));
dis[from] = 0;
pq.push(make_pair(0, from));
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (dis[u] < d) continue;
for (int i = 0; i < edges[u].size(); ++i) {
int v = edges[u][i].to;
int w = edges[u][i].dist;
char dir = edges[u][i].dir;
if (dir == 'N' && v > u || dir == 'S' && v < u || dir == 'E' && (v - u) % n == 1 || dir == 'W' && (u - v) % n == 1) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push(make_pair(dis[v], v));
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y, w;
char d;
cin >> x >> y >> w >> d;
edges[x].push_back({y, w, d});
edges[y].push_back({x, w, d});
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
dijkstra(i);
for (int j = 1; j <= n; ++j) {
if (dis[j] != INF && dis[j] > ans) {
ans = dis[j];
}
}
}
cout << ans << endl;
return 0;
}
```
在这个示例代码中,我们使用了一个邻接表来存储图的边信息。对于每条道路,我们将它的两个端点以及长度和方向存入邻接表中。在Dijkstra算法中,我们需要使用一个优先队列来维护当前到起点距离最小的农场,并且需要根据道路方向来判断是否能够到达目标农场。最后,我们遍历每个农场作为起点,求出距离最远的一对农场之间的距离,即为答案。
阅读全文