fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int C=105,oo=0x3f3f3f3f;
  4. int mp[C][C],cost[C],rt[C][C],u,v;
  5. map<string,int>cities;
  6. string s,su,sv;
  7. string cidx[C];
  8. int c,n,m,q,t;
  9. int main() {
  10.     scanf("%d",&t);
  11.     for(int tc=1;tc<=t;tc++){
  12.     if(tc-1) puts("");
  13.     printf("Map #%d\n",tc);
  14.     scanf("%d",&n);
  15.     for(int i=0;i<n;i++){
  16.         cin >> s >> c;
  17.         cities[s]=i;
  18.         cost[i]=c;
  19.         cidx[i]=s;
  20.     }
  21.     memset(mp,oo,sizeof mp);
  22.     scanf("%d",&m);
  23.     for(int i=0;i<m;i++){
  24.         cin >> su >> sv >> c;
  25.         mp[cities[su]][cities[sv]]=2*c;
  26.         mp[cities[sv]][cities[su]]=mp[cities[su]][cities[sv]];
  27.     }
  28.     for(int i=0;i<n;i++) mp[i][i]=0;
  29.     memset(rt,-1,sizeof rt);
  30.     for(int i=0;i<n;i++){
  31.         for(int u=0;u<n;u++){
  32.             for(int v=0;v<n;v++)
  33.                 if(mp[u][v]+cost[u]+cost[v]>mp[u][i]+mp[i][v]+cost[i]+cost[u]+cost[v]){
  34.                     mp[u][v]=mp[u][i]+mp[i][v];
  35.                     rt[u][v]=i;
  36.                 }
  37.         }
  38.     }
  39.     scanf("%d",&q);
  40.     for(int i=0;i<q;i++){
  41.     printf("Query #%d\n",i+1);
  42.         cin >> su >> sv >> c;
  43.         u=cities[su];
  44.         v=cities[sv];
  45.         if(su==sv){
  46.                 float f=cost[u];
  47.                 f+=f/10;
  48.                 f/=c;
  49.                 f*=100;
  50.                 round(f);
  51.                 f/=100;
  52.                 cout << su << endl;
  53.                 printf("Each passenger has to pay : %.2f taka\n",f);
  54.                 continue;
  55.         }
  56.         cout << su;
  57.         float f=mp[u][v]+cost[u]+cost[v];
  58.         int j=rt[u][v];
  59.                 while(j!=-1){
  60.                 cout << " " << cidx[j];
  61.                 f+=cost[j];
  62.                 j=rt[j][v];
  63.                 }
  64.         cout << " " << sv << endl;
  65.         f+=f/10;
  66.         f/=c;
  67.         f*=100;
  68.         round(f);
  69.         f/=100;
  70.         printf("Each passenger has to pay : %.2f taka\n",f);
  71.     }
  72.   }
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
1

1
limpopo 1
0
1
limpopo limpopo 1
stdout
copy 
Map #1
Query #1
limpopo
Each passenger has to pay : 1.10 taka
https://ideone.com/7e5YSu
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!