Input Your program will be tested on one or more test cases. The first line of each test case specifies three numbers (N , C , and R ) separated by one or more spaces. The city has N locations with distinct names, including the company's garage. C is the number of broken cars. R is the number of roads in the city. Note that 0 < N < 100 , 0<=C < 1000 , and R < 10000 . The second line is made of C + 1 words, the first being the location of the company's garage, and the rest being the locations of the broken cars. A location is a word made of 10 letters or less. Letter case is significant. After the second line, there will be exactly R lines, each describing a road. A road is described using one of these three formats:A -v -> BA <-v - BA <-v -> BA and B are names of two different locations, while v is a positive integer (not exceeding 1000) denoting the length of the road. The first format specifies a one-way street from location A to B , the second specifies a one-way street from B to A , while the last specifies a two-way street between them. A , ``the arrow", and B are separated by one or more spaces. The end of the test cases is specified with a line having three zeros (for N , C , and R .)The test case in the example below is the same as the one in the figure.
Output For each test case, print the total distance traveled using the following format:k . VWhere k is test case number (starting at 1,) is a space, and V is the result.
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 题目分析：题目思想不难，简单的floyd。前期数据处理相当有难度（对我来讲），有很多细节注意不到，而且题目很拗口，读了半天才明白 是个啥意思。主要有这么几点需要注意： 1.字符串转化为数字时那个提取数组结束符不要忘了加上。 2.对于修理厂要单独记录。这样方便破车数组记录。 3.对于floyd算法里面更新dist数组的判断，要注意加法dist[i][k]+dist[k][j]可能会溢出，要防止这样的bug程序出现。 只要注意到该注意的，只要有耐心写代码，这题一点都不难，难为我wa100多次了！ #include<cstdio> #include<cstring> #include<cctype> #include<map> #include<string> #include<algorithm> using namespace std; #define init(a,what) memset(a,what,sizeof(a)) #define read freopen("zx.in","r",stdin) #define write freopen("zx.out","w",stdout) #define INF 0x3f3f3f3f const int MAXN=1000+10; const int MAXM=100000+10; map<string,int>arr; int nnum,mnum,rnum,a,b,cminte; int dist[MAXN][MAXN],mm[MAXM]; char buf[MAXN],buf1[MAXN],buf2[MAXN],s[MAXN],ss[MAXN]; void floyd() { for(int k=1;k<=nnum;k++) for(int i=1;i<=nnum;i++) for(int j=1;j<=nnum;j++) //一定要判断dist两个数组不是无穷大（易错） if(dist[i][k]!=INF && dist[k][j]!=INF && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j]; } int main() { read, write; int ncase=1; while(scanf("%d%d%d",&nnum,&mnum,&rnum)!=EOF) { if(nnum==0 && mnum==0 && rnum==0) break; arr.clear(); init(dist,INF); int k=1; scanf("%s",buf); arr[buf]=k++;//修理厂要单独处理！（这里wa了十多次） for(int i=1;i<=mnum;i++) { scanf("%s",buf); if(!arr[buf]) arr[buf]=k++; mm[i]=arr[buf];//mm[]记录破车编号 } for(int l=1;l<=rnum;l++) { scanf("%s%s%s",buf1,s,buf2); int len=strlen(s); if(!arr[buf1]) a=arr[buf1]=k++; else a=arr[buf1]; if(!arr[buf2]) b=arr[buf2]=k++;//这里也容易出错 else b=arr[buf2]; int cnt=0; bool temp[2]={false,false}; for(int i=0;i<len;) { if(s[i]=='>') temp[0]=true; if(s[i]=='<') temp[1]=true; while(isdigit(s[i])) { ss[cnt]=s[i]; cnt++, i++; } ss[cnt]='/0';//记得使得字符数组结束（易错） i++; } sscanf(ss,"%d",&cminte);//要熟练掌握ssacnf函数 if(temp[0] && dist[a][b]>cminte) dist[a][b]=cminte; if(temp[1] && dist[b][a]>cminte) dist[b][a]=cminte; } floyd(); int sum=0; for(int i=1;i<=mnum;i++) sum+=(dist[1][mm[i]]+dist[mm[i]][1]);//注意走过去还要在拖回来 printf("%d. %d/n",ncase++,sum); } return 0; }
