# 用Dijkstra算法求解无向图的最短路径

Dijkstra 算法是典型的算法。Dijkstra 算法是很有代表性的算法。Dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 OPEN, CLOSE 表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

# ACM刷题之-POJ-1002(487-3279)

Description Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino’s by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. Yo

# ACM刷题之-POJ-1011(Sticks)

Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero. Input The input contains blocks of 2 lines. The first line con

# ACM刷题之-POJ-1014(Dividing)

Description Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbl

# ACM刷题之-POJ-1061(青蛙的约会)

Description 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 Input 输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 21

# ACM刷题之-POJ-1396(Simple Arithmetics)

Description One part of the new WAP portal is also a calculator computing expressions with very long numbers. To make the output look better, the result is formated the same way as is it usually used with manual calculations. Your task is to write the core part of this calculator. Given two numbers and the requested operation, you are to compute the result and print it in the form specified below. With addition and subtraction, the numbers are written below each other. Multiplication

# ACM刷题之-POJ-2192(Zipper)

Description Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming “tcraete” from “cat” and “tree”: String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee

# ACM刷题之-POJ-3749(破译密码)

Description 据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F）。而你要获得消息原文，也就是要将这个过程反过来。 密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M 原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 注意：只有字母会发生替换，其他非字母的字符不变，并且消息原文的所有字母都是大写的。 Input 最多不超过100个数据集组成，每个数据集之间不会有空行，每个数据集由3部分组成: 起始行：START 密码消息：由1到200个字符组成一行，表示凯撒发出的一条消息. 结束行：END 在最后一个数据集之后，是另一行：ENDOFINPUT Output 每个数据集对应一行，是凯撒的原始消息。 Sample Input START NS BFW, JA

# ACM刷题之-POJ-1191(棋盘分割)

Description 将一个 ８* ８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差，其中平均值，xi 为第 i 块矩形棋盘的总分。 请编程对给出的棋盘及 n，求出 O'的最小值。 Input 第 1 行为一个整数 n(1 < n < 15)。 第 2 行至第 9 行每行为 8 个小于 100 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。 Output 仅一个数，为 O'（四舍五入精确到小数点后三位）。 Sample Input 3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

# ACM刷题之-POJ-3662(Telephone Lines)

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart. The i-th cable

# ACM刷题之-POJ-3333(Co-workers from Hell)

Description A watchman has to check a number of chambers in the factory each night according to a schedule which specifies the order in which the chambers must be visited and the time it takes to check each chamber. The watchman starts his job each night starting from the first chamber and leaves the factory and goes home when he checks the final chamber. He normally checks all other chambers, but in our story he may not actually do so. Having access to this schedule, a co-worker wants to

# ACM刷题之-POJ-3006(Dirichlet's Theorem on Arithmetic Progre)

Description If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, …, contains infinitely many prime numbers. This fact is known as Dirichlet’s Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837. For example, the arithmetic sequence beginning with 2 and i