超难.................(能做出来智商起码150)

工儯新一

第一章 胜利的逃亡

Time Limit:2s Memory Limit:32768k

Problem

来自异空的精灵族为这个世界带来了秩序。为了与不断侵犯的邪恶力量作战，万神殿选中了他们最强大的战士Prince与Gush作为他们的守护战神。他们在上百万年的时间里一丝不苟地履行着自己的职责，搜寻并摧毁一切能找到的恶魔。终于有一天在艾泽拉斯遭遇了两支从实体世界中获得了巨大能量的强大恶魔种族。兵败后他们被关在恶魔之都的地下监狱里。
漫长的等待后终于获得了一个逃跑计划。这能够使两位战神跑到恶魔之都的传送点。然后一同回自己的世界。首先Gush沿着城市的街道跑到传送点。然后发送超声信号给Prince，告诉Prince应该跑到哪里。然后Prince沿着街道跑到相同地点，与Gush会合，接着秘密传送回自由的领地。
Gush穿着精灵族的铠甲行走，所以会引起路上恶魔的注意。所以Prince的行程不能与Gush相同。即Gush走过的街Prince不能再走。你需要计算从Gush离开监狱到Prince到达传送点的最短时间。假设发送消息不花费任何时间。

简而言之：
给你一个有权的无向图，找到两条最短的从S到T的路，使得每条街最多走了一次。输出他们最短的时间之和。


Input

本题含有多组数据。每组数据开头为n (2<=n<=100)（街道交点的个数-即结点个数）。监狱在结点1，传送点在结点n。下一行为街道个数m。接着m行描述这m条街。每行有三个整型变量a b t，a b为这条街连接的两个结点号，t (1<=t<= 1000)为走过这条街道需要的时间。每条街连接两个不同的结点。每两个结点之间不会有多条街道。最后一组数据后为一个0。

Output

对于每组数据输出从Gush离开监狱到Prince到达传送点的最短时间。如果无解则输出一行"Back to jail"。

Sample Input

2 1 1 2 999 3 3 1 3 10 2 1 20 3 2 50 9 12 1 2 10 1 3 10 1 4 10 2 5 10 3 5 10 4 5 10 5 7 10 6 7 10 7 8 10 6 9 10 7 9 10 8 9 10 0 Sample Output

Back to jail 80 Back to jail 要把程序打出来

daat1928

好难  最后的程序什么意思呢？

haoshouzheng

我明白了!

≡怪盗缺德≡

题目记下
考虑去了~~

笨笨小怪盗

%&051  这是什么啊！？~
恐怕是要学程序的人 才会做出来吧%&072

Thinking......

jiabailie

还真不会

二十面相

n是固定的吗？结点n是几啊？

牧龙客

看不懂题目耶，好像要专业知识的说，唉，那就不知道自己智商是否有150了

工儯新一

[QUOTE=haoshouzheng]我明白了![/QUOTE]

那请说吧.

黑羽留姬

看不懂~~~

Dark Angel

这题用坐标曲线图解析会不会简单一点呢？~如果先设起点为坐标原点0，则三个整型变量a b t中的两个坐标函数会交于一点，则这一点为终点，由于这一点是变量，则图形为双曲线一项半轴图，在图中取离坐标原点最近的点的值为终点~则XY值分别为甲乙两人所经过的路程~
还有一种解法就是设终点为坐标原点······就解到这了，得数个位ZT们努力计算把~画出图回简单很多~

黑羽留姬

哦?用折线图就能解了吗?试试~~

工儯新一

加油哦!各位.

黑羽留姬

恩~好像是函数题~~很多术语没学过,解不出来~~~
有权的无向图——这是什么？？

工藤￥新一

无项图最短路径是不是编程？

SP(Shortest Path，最短路径)问题是编程中最常见的问题之一，下面介绍2个计算最短路径的算法。
输入文件格式：
第一行：n，代表端点数
第2到n+1行：邻接矩阵

一、Floyd-Warshall算法
　　该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即：
　　Dij=min(Dij,Dik+Dkj，……)，1<=k<=5。
　这样，我所就找到了一个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径

程序如下：
CLS
CONST max = 200
CONST maxn = 30
DIM SHARED n, s, f
DIM SHARED map(maxn, maxn)
CALL init
CALL floyd
CALL show

SUB floyd
FOR k = 1 TO n
FOR i = 1 TO n
FOR j = 1 TO n
   IF map(i, j) > map(i, k) + map(k, j) THEN
      map(i, j) = map(i, k) + map(k, j)
   END IF
NEXT j, i, k
END SUB

SUB init
INPUT "File Name:", fin$
OPEN fin$ FOR INPUT AS #1
INPUT #1, n
FOR i = 1 TO n
FOR j = 1 TO n
  INPUT #1, map(i, j)
NEXT j, i
FOR i = 1 TO n
FOR j = 1 TO n
  IF map(i, j) = 0 THEN map(i, j) = max
NEXT j, i
INPUT "Starting Point:", s
INPUT "Finishing Point:", f
END SUB

SUB show
PRINT "The Shortest Length From "; s; " to "; f; " is "; , map(s, f)
END SUB

这个算法是常用的算法之一，复杂度为O(n^3)


二、Dijkstra算法（类似标号法，一般不作区分）
所谓标号法的基本思想是从起点s出发，逐步地向外探寻最短路。在执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从s到该点的最短路的权（称为P标号），或者表示这个权的上界（称为T标号），具体做法是每扩展一步，就将一个具T标号的点改具P标号的点，从而使有向图D中具P标号的顶点数增多一个。如此一步步执行下去，就可求出从s到各点的最短路。
程序如下：
CLS
CONST maxn = 50
DIM SHARED n, s, f
DIM SHARED map(maxn, maxn), dis(maxn), mark(maxn)      
'mark记录是否已被标号，dis存s到各点的距离。
CALL init        '初始化
CALL dijkstra      '主过程
CALL show       '输出
END

SUB dijkstra
DO
  bv = 0
  FOR i = 1 TO n
    IF mark(i) THEN
      FOR j = 1 TO n
        IF mark(j) = 0 AND map(i, j) THEN
          IF bv = 0 OR dis(i) + map(i, j) < bv THEN
            bv = dis(i) + map(i, j)
            bn = j
          END IF
        END IF
      NEXT j
    END IF
  NEXT i
  IF bv > 0 THEN
    mark(bn) = 1
    dis(bn) = bv
  END IF
LOOP UNTIL bv = 0
END SUB

SUB init
INPUT "File Name:", fin$
OPEN fin$ FOR INPUT AS #1
INPUT #1, n
FOR i = 1 TO n
FOR j = 1 TO n
  INPUT #1, map(i, j)
NEXT j
NEXT i
CLOSE
INPUT "Starting Point:", s
INPUT "Finishing Point:", f
mark(s) = 1
END SUB

SUB show
PRINT "The Shortest Length From "; s; " to "; f; " is "; dis(f)
END SUB

N/A

[QUOTE=火翼天使]还没有回答我的问题，不知道用蒂克斯拉算法可不可以，最近忙着考试没有太仔细想。[/QUOTE]



雖然沒有什麽難度,但考慮到程序優化,仍然可以做調整

http://acm.tongji.edu.cn/people/ps/problem.php?from=1100
做完的去同濟那裏提交吧