fork download
  1. #include<iostream>
  2. #include<map>
  3. #include<string.h>
  4. using namespace std;
  5. int counti=0;
  6. int main()
  7. {
  8. int n,c,r;
  9. int wt[102][102];
  10. cin>>n>>c>>r;
  11. while(n!=0||c!=0||r!=0)
  12. {
  13. counti++;
  14. char src[16];
  15. int count=1;
  16. map<string,int> mymap;
  17. for(int i=1;i<=n;i++)
  18. for(int j=1;j<=n;j++)
  19. {
  20. if(i==j)
  21. wt[i][j]=0;
  22. else wt[i][j]=10002;
  23. }
  24. cin>>src;
  25. mymap[src]=count;
  26. count++;
  27. char d[16];
  28. int w=0;
  29. char arr[2005][16];
  30. while(c--)
  31. {
  32. cin>>d;
  33. mymap[d]=count++;
  34. strcpy(arr[w],d);
  35. w++;
  36. }
  37. char a[16],b[16],v[16];
  38. while(r--)
  39. {
  40. cin>>a>>v>>b;
  41. if(!mymap[a])
  42. mymap[a]=count++;
  43. if(!mymap[b])
  44. mymap[b]=count++;
  45. int num=0,k=2;
  46. while(v[k]>='0'&&v[k]<='9')
  47. {
  48. num*=10;
  49. num+=v[k]-'0';
  50. k++;
  51. }
  52. int len=strlen(v);
  53. if(v[0]=='-')
  54. wt[mymap[a]][mymap[b]]=num;
  55. else if(v[0]=='<'&&v[len-1]=='>')
  56. {wt[mymap[a]][mymap[b]]=num;
  57. wt[mymap[b]][mymap[a]]=num;
  58. }
  59. else wt[mymap[b]][mymap[a]]=num;
  60. }
  61.  
  62. for(int g=1;g<=n;g++)
  63. {
  64. for(int h=1;h<=n;h++)
  65. {
  66. for(int l=1;l<=n;l++)
  67. {
  68. if(wt[h][l]>wt[h][g]+wt[g][l])
  69. wt[h][l]=wt[h][g]+wt[g][l];
  70. }
  71. }
  72. }
  73. long long ans=0;
  74. for(int i=0;i<w;i++)
  75. {
  76. ans+=wt[1][mymap[arr[i]]];
  77. ans+=wt[mymap[arr[i]]][1];
  78. }
  79. cout<<counti<<". "<<ans<<endl;
  80. cin>>n>>c>>r;
  81. }
  82. return 0;
  83. }
  84.  
Success #stdin #stdout 0s 3248KB
stdin
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
stdout
1. 80