1087 All roads 最短路径算法，所有的最短路径，各种回溯
这是我最近写过的最丑的代码，没有之一。太繁琐，变量名都起不过来，只能加注释，顾不上那么多了。发现所有 test case 都过了的时候我简直惊呆了。
在dijkstra最短路算法的基础上，对于路径一样长的情况都要存下来。
然后就可以递归回溯各种可能的路径，寻找happiness最大的或者平均happiness最大的。这里
# include <cstdio>
# include <cstring>
int N, K; //number of cities, number of roads
int dest;
int happy[200];
int cost[200][200];
char name[200][4];
int p[200][200]; //id of the city's parent
int np[200]; //number of parents
int dist[200]; // total cost of coming
bool status[200]; //if its shortest dist is known
int nRoute = 0; //有多少条路线是最短路
int h, mh; //当前路线的happy, 最优路线的happy
int nNode, mnNode; //当前经历的节点，最优路线的节点数
int route[200], mRoute[200]; //当前路线，最优路线
int id(char *str) {
for (int i = 0; i < N; i++) {
if (strcmp(str, name[i]) == 0) {
return i;
}
}
return -1;
}
void read() {
scanf("%d %d %s", &N, &K, name[0]); //start point at 0
for (int i = 1; i < N; i++) {
scanf("%s %d", name[i], happy + i);
}
dest = id("ROM");
//init the graph
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cost[i][j] = 1 << 30;
}
cost[i][i] = 0;
dist[i] = (1 << 30);
}
for (int i = 0; i < K; i++) {
char a1[4], a2[4];
int d, ia1, ia2;
scanf("%s %s %d", a1, a2, &d);
ia1 = id(a1); ia2 = id(a2);
cost[ia1][ia2] = (cost[ia2][ia1] = d);
}
}
void dijk() {
dist[0] = 0;
while (1) {
int m = 0, md = 1 << 30; //m = 最短路径未知的集合里距离最小的点
for (int i = 0; i < N; i++) {
if (!status[i] && dist[i] < md) {
md = dist[i];
m = i;
}
}
if (m == 0 && status[0]) { //说明所有的点 status 都为真了，所以m才没变
break;
}
status[m] = true; // 最短路已知
for (int i = 0; i < N; i++) {
if (!status[i] && cost[m][i] < (1 << 30)) { //有路
if (cost[m][i] + dist[m] < dist[i]) { //比之前的路更短
np[i] = 1;
p[i][0] = m;
dist[i] = cost[m][i] + dist[m];
}
else if (cost[m][i] + dist[m] == dist[i]) { //和之前的路一样短
p[i][(np[i] ++)] = m;
}
}
}
}
}
void backward(int x) {
route[nNode++] = x;
h += happy[x];
if (x == 0) { //回溯到了起点
nRoute++;
if (h > mh || (h == mh && (h / (float)nNode) > (mh / (float)mnNode))) { //更好的路线
mh = h;
mnNode = nNode;
memcpy(mRoute, route, sizeof(int) * 200);
}
}
else {
for (int i = 0; i < np[x]; i++) { //i的每一个祖先
backward(p[x][i]);
}
}
h -= happy[x];
nNode--;
}
int main() {
read();
dijk();
backward(dest);
printf("%d %d %d %d\n", nRoute, dist[dest], mh, mh / (mnNode - 1));
for (int i = mnNode - 1; i >= 1; i--) {
printf("%s->", name[mRoute[i]]);
}
printf("%s", name[mRoute[0]]);
return 0;
}
1086. Tree Traversals Again 中序遍历的逆向，后序遍历
给了一堆做中序遍历时的 push 和 pop 的命令，要求输出后续遍历。
先从操作逆推了一棵树。写中序遍历的时候，对左孩子入栈，一直到没有左孩子为止，然后出栈后找右孩子。因此找到了规律，如果操作是 push，那下一步准备插入的位置就是它的左子树（如果下一步不是 push 就算了）；如果 pop 了一个，那么下一步准备插入的位置是它的右子树。逻辑想了半天，写起来很简单。
恰好节点的 key 都是 1-N的，我就不开树了，直接拿几个数组存下来，免得还得根据 key 查找节点的位置，多麻烦。
最后做一个后序遍历，很简单，过了。
1085. Perfect Sequence
很简单的逻辑，简单到我有点不会做了，卡了半天。
1084. Broken Keyboard
也很简单，按照顺序比对字符就可以了。注意指针怎么向后挪。记一下缺少的键是否输出过了。
1083. List Grades 过于简单
结构体，排个序，输出。本来以为肯定超时，结果case也很弱……
1082 read number in Chinese 复杂逻辑
给出不多于9位的数字，要输出汉语读法。刚开始的思路是每4位读一下，最后结合到一起，结果发现逻辑太复杂了，前面0，后面0，中间两个0，写得很晕。
最终的写法是，先识别不同位置的 0，该跳过还是读一次。标记完 0 之后就很简单了，打表输出。贴代码如下：
# include <cstdio>
# include <cstring>
char digits[10][6] = { "ling ", "yi ", "er ", "san ", "si ", "wu ", "liu ", "qi " , "ba ", "jiu " };
char pos[9][6] = { "", "Qian ", "Bai ", "Shi ", "", "Qian ", "Bai ", "Shi ", "" };
char result[9][20];
char num[11];
int len;
int main() {
scanf("%s", num);
if (num[0] == '-') {
printf("Fu ");
for (int i = 0; num[i] != '\0'; i++) {
num[i] = num[i + 1];
}
}
len = strlen(num);
int i = 0;
while (num[i] == '0' && i < len) { //刚开始的0要跳过
num[i] = 's'; //skip
i++;
}
int start = i; //除去0后数字真正开始的地方
i = len - 1;
while (num[i] == '0' && i >= 0) { //最后的0也跳过
num[i] = 's';
i--;
}
i = len - 5;
while (num[i] == '0' && i >= 0) { //万位及之前相邻的跳过
num[i] = 's';
i--;
}
i = 0;
while (i < len) { //其它地方连0都读一个0
if (num[i] == '0') {
num[i] = 'r'; //read
i++;
while (num[i] == '0' && i < len) {
num[i] = 's';
i++;
}
}
i++;
}
char read[200] = "";
for (i = 0; i < len; i++) {
if (num[i] >= '1' && num[i] <= '9') {
strcat(read, digits[num[i] - '0']);
strcat(read, pos[i + 9 - len]);
}
else if (num[i] == 'r') {
strcat(read, digits[0]);
}
if (i >= start && i + 9 - len == 0) { //到了亿位
strcat(read, "Yi ");
}
if (i >= start && i + 9 - len == 4) { //到了万位
strcat(read, "Wan ");
}
}
if (strlen(read) == 0) { //输入的是0
strcpy(read, "ling");
}
else {
read[strlen(read) - 1] = '\0';
}
printf("%s", read);
return 0;
}
//Fu yi ba er jiu san Yi si Qian wu Bai liu Shi qi Wan ba Qian jiu Bai
//Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu
1081. Rational Sum 简单
和 1088 的要求很相似，甚至还变简单了。刚开始跑出了浮点错误，后来看论坛发现是 gcd（） 里面没有判断有 0 的情况，有 0 直接返回 1 就可以了。
1079. Total Sales of Supply Chain 超时
题目很简单，一棵树，最后需要一些节点的深度。刚开始我是用 bfs 把所有节点的深度记了一遍，发现超时严重；后来改成需要哪个的深度，就递归往爹娘求，一直求到根节点。结果还是有一个case超时。我把后面需要用的 pow(x, y) 打表了一遍，那个case还是超时。
