【floyd/要防重边】HDU 2923 Einbahnstrasse

基德KID.1412

http://acm.hdu.edu.cn/showproblem.php?pid=2923

一开始题意理解错了……英语太水了
要从公司开始按所给顺序把车拉回来，是一辆一辆车拖回来……这是常识……我竟然想着最后一堆车拖回来


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[M][M], ind[M];void init (){    m.clear();    int i, j;    for (i = 1; i <= n; i++)        for (j = i + 1; j <= n; j++)            dist[j] = dist[j] = 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[k] + dist[k][j] < dist[j])                    dist[j] = dist[k] + dist[k][j];}int main(){    int c, r, i, key, w, res, cc = 1, len, k, j, u, v;    bool flag, mark;    char s1[15], s2[15], s[15], tp[15];    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[p] == 0)                m[p] = key++;    //将字符串p映射为key【编号】            ind = m[p];        }        for (i = 0; i < r; i++)        {            flag = mark = false;            scanf ("%s%s%s", s1, s, s2);            string p1(s1);            if (m[p1] == 0)                m[p1] = key++;            u = m[p1];            string p2(s2);            if (m[p2] == 0)                m[p2] = key++;            v = m[p2];            len = strlen(s);            k = 0;            for (j = 0; j < len; j++)            {                if (s[j] == '<') flag = true;                if (s[j] == '>') mark = true;                if (s[j] >= '0' && s[j] <= '9')                    tp[k++] = s[j];    //tp读取箭头中间的数字            }            tp[k] = 0;            sscanf (tp, "%d", &w);    //tp转化成int存放到w            if (flag && w < dist[v]) dist[v] = w;            if (mark && w < dist[v]) dist[v] = w;//记得判断重边【w < dist[v]】，wa了无数次        }        floyd();        res = 0;        for (i = 1; i <= c; i++)            res += (dist[1][ind] + dist[ind][1]);//先从1去那里，再把车拉回1，根据题意，是按顺序一个一个拖回来        printf ("%d. %d\n", cc++, res);    }    return 0;}