输入格式:第一行是两个以空格符分隔的整数n和m;接下来的第二行到第m+1行,每行包含4个以空格分开的元素x,y,w和d来描述一条道路,其中x和y是一条长度为w的道路相连的两个农场的编号,d是字符N.E.S.或W,表示从x到y的道路的方向。输出格式:给出最远的一对农场之间距离的整数。
时间: 2023-12-14 16:37:09 浏览: 117
这是一个图论问题,可以使用Dijkstra算法或Floyd算法求解最短路。但是题目要求的是最远距离,可以将每条边的边权取负数,然后再使用Dijkstra或Floyd算法求解最短路,最后将结果取相反数即为最远距离。
下面是使用Dijkstra算法的示例代码:
```python
import heapq
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
x, y, w, d = input().split()
x, y, w = int(x), int(y), int(w)
if d == 'N':
graph[x].append((y, -w))
graph[y].append((x, -w))
elif d == 'E':
graph[x].append((y, w))
graph[y].append((x, -w))
elif d == 'S':
graph[x].append((y, w))
graph[y].append((x, w))
else:
graph[x].append((y, -w))
graph[y].append((x, w))
def dijkstra(start):
dist = [float('inf')] * (n+1)
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
farthest = max(dijkstra(1))
print(-farthest)
```
在上面的代码中,建立了一个有向图,根据输入的方向将边权取反。然后使用Dijkstra算法求出从第一个农场到其他农场的最短距离,再取相反数得到最远距离。
阅读全文