【floyd/要防重边】HDU 2923 Einbahnstrasse
http://acm.hdu.edu.cn/showproblem.php?pid=2923一开始题意理解错了……英语太水了
要从公司开始按所给顺序把车拉回来，是一辆一辆车拖回来……这是常识……我竟然想着最后一堆车拖回来
http://dl.iteye.com/upload/attachment/537526/9e966ac9-fafa-34de-ba6a-6ddbf73378dc.jpg
Sample Input
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale--5-> Bakerline
0 0 0
Sample Output
1. 80
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define inf 0x3fffffff#define M 1005map<string, int> m;int n, dist, ind;void init (){ m.clear(); int i, j; for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) dist = dist = inf;}void floyd (){ int i, j, k; for (k = 1; k <= n; k++) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) if (dist + dist < dist) dist = dist + dist;}int main(){ int c, r, i, key, w, res, cc = 1, len, k, j, u, v; bool flag, mark; char s1, s2, s, tp; while (scanf ("%d%d%d", &n, &c, &r), (n||c||r)) { key = 1; init (); for (i = 0; i <= c; i++) { scanf ("%s", s); string p(s); if (m == 0) m = key++; //将字符串p映射为key【编号】 ind = m; } for (i = 0; i < r; i++) { flag = mark = false; scanf ("%s%s%s", s1, s, s2); string p1(s1); if (m == 0) m = key++; u = m; string p2(s2); if (m == 0) m = key++; v = m; len = strlen(s); k = 0; for (j = 0; j < len; j++) { if (s == '<') flag = true; if (s == '>') mark = true; if (s >= '0' && s <= '9') tp = s; //tp读取箭头中间的数字 } tp = 0; sscanf (tp, "%d", &w); //tp转化成int存放到w if (flag && w < dist) dist = w; if (mark && w < dist) dist = w;//记得判断重边【w < dist】，wa了无数次 } floyd(); res = 0; for (i = 1; i <= c; i++) res += (dist] + dist]);//先从1去那里，再把车拉回1，根据题意，是按顺序一个一个拖回来 printf ("%d. %d\n", cc++, res); } return 0;}
页:
[1]