深爱Dijkstra

发布时间: 2017年6月19日 00:24   时间限制: 4000ms   内存限制: 128M

   话说小豪认识Dijkstra算法还要追溯到去年寒假,那时候的小豪看着严奶奶的视屏教程才懵懵懂懂了解了Dijkstra是一个求最短路的算法。从那以后小豪和Dijkstra的故事一直在继续,就在前一段时间的acm课上小豪还详细讲解了他自己的Dijkstra模版。现在小豪需要考考你掌握Dijkstra到什么程度?小豪给出了一个无向图(小豪温馨提示:会有自环和重边)无向图中有n个结点,m条边。现在小豪需要求出所有结点之间最短路之和(若是两个结点间不能到达那么算成是x)例:n=2时 ans = d(1,1)+d(1,2)+d(2,1)+d(2,2)。然后小豪会从图中随机拿去一条边然后在让你计算所有结点之间最短路之和,问你可能得到的最大值是什么?

输入数据有多组,每组数据的第一行包含三个整数n(1<n<=100), m(1<m<=1000),x(1<=x<=1e9)。接下来有m行每行三个数 a, b,(1<=a,b<=n) c(1<=c<=1e9)分别表示a与b之间有一条路径长度为c,输入至文件结束。

输出数据占一行包含两个整数以空格分开,先输出原来最短路之和,在输出拿去一条边后可能的最大值。

复制
4 6 1000
1 3 2
1 4 4
2 1 3
2 3 3
3 4 1
4 2 2
28 38
1720

old_judge

old_judge_None