首页 > 代码库 > hdu 2923

hdu 2923

最短路加字符串处理

#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <cstring>#include <cstdlib>#include <map>using namespace std;#define N 2005#define INF 0x3f3f3f3f#define LL __int64#define INF 0x3f3f3f3fchar s1[20],s2[20],s3[20],s[1005][20];int ma[N][N],d[N],vis[N];void flody(int n){    int i , j, k;    for(k = 1 ; k <= n ; k++)    {        for(i = 1 ; i <= n ; i++)        {            if(ma[i][k]!=INF)            {                for(j = 1 ; j<=n ; j++)                if(ma[i][k]+ma[k][j]<ma[i][j]) ma[i][j] = ma[i][k]+ma[k][j];            }        }    }}int main(){    int n,i,j,k,c,r,num ,cas = 1;    map<string,int>m;    while(~scanf("%d %d %d",&n,&c,&r),n+c+r)    {        num = 1;        m.clear();        for(i = 1 ; i <= c+1;i++)        {            scanf("%s",s[i]);            if(!m[s[i]])            m[s[i]] = num++;        }        for(i = 1; i<= N ;i++)            for(j = 1; j<= N ;j++)            ma[i][j] = (i==j)?0:INF;        for(i = 1; i<= r ; i++)        {            scanf("%s %s %s",s1,s2,s3);            int ans = 0,len2 = strlen(s2),x,y;            for(j = 0 ; j < len2 ; j++)                if(s2[j]>=0&&s2[j]<=9) ans = ans*10+s2[j] - 0;                if(!m[s1]) m[s1] = num++;                if(!m[s3]) m[s3] = num++;                x = m[s1];                y = m[s3];            if(s2[0]==<&&s2[len2-1]==>){                if(ma[x][y]>ans)                    ma[x][y]  = ans;                if(ma[y][x]>ans) ma[y][x] = ans;            }else if(s2[0]==<){                if(ma[y][x]>ans)            ma[y][x] = ans;            }else if(ma[x][y]>ans) ma[x][y] = ans;        }            flody(num);            int sum = 0,p;            for(i = 2 ; i <=c+1;i++)                sum+=ma[m[s[i]]][1]+ma[1][m[s[i]]];            printf("%d. %d\n",cas++,sum);    }    return 0;}