PID398 / Mato完整版学体育
题目描述

背景

Mato完整版在体育课绕方形操场跑步时总是沿对角线跑……这让他的体育老师很恼怒……

描述

体育老师为了惩罚他,将他带到了一个迷宫中。这个迷宫有n个节点和m条边(1<=n,m<=100000)。数据保证是连通无向图。

Mato完整版被安排在节点1处。其余n-1个节点都有体育老师。(四十五中哪儿来这么多体育老师?)Mato完整版被要求跑到第一个老师面前,再跑回节点1,再跑到第二个老师面前,再跑回节点1……直到每个老师所在节点都跑一次(最后还要回节点1)。

(体育老师p.s.:有本事你再沿最短路径跑啊!)

Mato完整版的确准备沿最短路径跑。但他跑的路程的总和(即节点1到其他节点的最短路径之和乘2)不能超过(小于等于)极限t,否则他就要选择逃跑。现在请你求出他跑的路程的总和,使他决定到底是跑还是逃。

输入格式

第一行是三个数:n,m,t。(1<=t<=7000000000)

以下m行,每行三个数:a,b,s,表示节点a与节点b之间的路程是s(1<=s<=100)。

输出格式

第一行是Mato完整版跑的路程的总和,如果超过t,则第二行输出“escape”,如果没超过,则第二行输出“run”。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论