NC216216. 最长的最短路
描述
小张是个邮递员，一直以来他都骑着他的小电驴送邮件。今天小张终于攒够了钱去买一辆新车！可是今天仍然是工作日，因此小张只能在完成了今天的邮件投递任务之后才能去买车。因为想要早点下班去买车，小张决定研究一下每个要前往的投递点与邮局所在的点最短路是多远。因此小张将每个投递点重新编号为1~N，邮局所在地点编号为0。并且直接画出了有些投递点之间的M条单行路，最终得到了一张新的地图，小张想知道距离邮局最远的投递点是哪个（如果某个投递点不可达则不用考虑该距离）。
输入描述
输入N（N< 1e4）代表有N个投递点（编号为1~N），与M(M<1e5)条路。接下来M行，每行含三个值：u，v，w，代表u，v之间有一条单行路，从u可以到达v。投递点这两个投递点，路的长度为w（w <= 1e9）。
输出描述
输出投递点中到邮局的最短路径最长的一个，并且输出这个投递点的编号。如果有多个答案，输出编号最小的投递点。
示例1
输入:
4 4 0 1 4 0 2 3 0 3 2 0 4 1
输出:
4 1
pypy3 解法, 执行用时: 621ms, 内存消耗: 33852K, 提交时间: 2023-04-29 19:17:55
import heapq
n,m=map(int,input().split())
a=[[] for i in range(n+1)]
for i in range(m):
u,v,w=map(int,input().split())
a[u].append((v,w))
dis=[0]+[10**10]*n
vis=[0]*(n+1)
def dijtsra():
queue=[(0,0)]
while queue:
d,u=heapq.heappop(queue)
if vis[u]==1:
continue
vis[u]=1
for v,w in a[u]:
if d+w<dis[v]:
dis[v]=d+w
heapq.heappush(queue,(dis[v],v))
max=-10**10
res=0
k=0
dijtsra()
for i in range(1,n+1):
if vis[i] and dis[i]>res:
res=dis[i]
k=i
print(res,k)
C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 388K, 提交时间: 2021-03-09 16:38:16
#include<bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int u, v, w;
cin >> u >> v >> w;
int this_post = v, this_road = w;
N = N - 1;
while (N--) {
cin >> u >> v >> w;
if (w >= this_road) {
if (v < this_post) {
v = this_post;
w = this_post;
}
}
cout << this_road << " " << this_post << endl;
break;
}
return 0;
}
Python3(3.9) 解法, 执行用时: 56ms, 内存消耗: 2936K, 提交时间: 2021-03-09 15:56:45
n,m=map(int,input().split())
ls=[]
for i in range(n):
u,v,w=map(int,input().split())
if u==0:
ls.append([u,v,w])
ls.sort(key=lambda x:x[2],reverse=True)
max1=ls[0][2]
min1=n
j=0
while ls[j][2]==max1:
min1=min(min1,ls[j][1])
j+=1
print(max1,min1)