Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define pf(x) printf("%d",x)
- #define pfd(x,y) printf("%d %d",x,y)
- #define pfl(x) printf("%ld",x)
- #define nl printf("\n")
- #define cs(x) printf("Case %d: ",x)
- #define csn(x) printf("Case %d:\n",x)
- #define all(x) x.begin(),x.end()
- #define Find(x,n) find(all(x),n)
- #define pi acos(-1.0)
- #define i64 long long
- #define pb(x) push_back(x)
- #define mset(x,v) memset(x,v,sizeof(x))
- #define sc(n) scanf("%d",&n)
- #define scl(n) scanf("%ld",&n)
- #define scll(n) scanf("%lld",&n)
- #define scd(n,m) scanf("%d %d",&n,&m)
- #define scdl(n,m) scanf("%ld %ld",&n,&m)
- #define scdll(n,m) scanf("%lld %lld",&n,&m)
- #define filein freopen("in.txt","r",stdin)
- #define fileout freopen("my.txt","w",stdout)
- #define FOR(i,n) for(int i=0;i<n; i++)
- #define inf 20000000.0
- bool isUpper(char ch){ if( ch>='A' && ch<='Z' ) return true; return false; }
- bool isLower(char ch){ if( ch>='a' && ch<='z') return true; return false;}
- bool isLetter(char ch){ if( ch>='A' && ch<='Z' || ch>='a' && ch<='z') return true; return false; }
- bool isDigit(char ch){ if( ch>='0' && ch<='9') return true; return false; }
- char toLower(char ch){ if (isUpper(ch)) return (ch+32); return ch; }
- char toUpper(char ch){ if (isLower(ch)) return (ch-32); return ch; }
- template<class T>bool isEven(T a){ return (a%2==0);}
- template<class T>T sq(T a){ return a*a; }
- template<class T>T gcd(T a,T b){ return b==0 ? a : gcd(b,a%b); }
- template<class T>T lcm(T a,T b){ return (a/gcd(a,b))*b; }
- template<class T>bool isPrime(T n){ for(T i=2; i*i<=n; i++){ if(n%i==0) return false; } return true; }
- template<class T>T Pow(T n,T p) { T res=n; for(T i=1;i<p; i++){ res *= n; } return res; }
- template<class T>T Max(T n,T p) { if(n>=p) return n; return p; }
- float g[23][23];
- int next[23][23];
- map<int,string>idint;
- map<string,int>idst;
- float paid[23];
- void floyd_warshall(int n){
- for(int k=1;k<=n; k++)
- for(int i=1;i<=n; i++)
- for(int j=1;j<=n; j++)
- if( g[i][j]>(g[i][k]+g[k][j]) )
- g[i][j]=g[i][k]+g[k][j],next[i][j]=next[i][k];
- }
- void Set(int n){
- for(int i=1;i<=n; i++)
- for(int j=1;j<=n; j++)
- g[i][j]=inf,next[i][j]=j;
- }
- void Setpay(int n){
- for(int i=1;i<=n; i++)
- for(int j=1;j<=n; j++)
- g[i][j] += paid[j];
- }
- void printPath(int u,int v){
- printf("%s",idint[u].c_str());
- while(u!=v){
- u = next[u][v];
- printf(" %s",idint[u].c_str());
- }
- nl;
- }
- int main()
- {
- //filein;
- int T=0,t;
- sc(t);
- while( t-- ){
- int nStation,nPath,nQuery;
- sc(nStation);
- Set(nStation);
- for(int i=1;i<=nStation;i++){
- cin >> idint[i];
- scanf("%f",&paid[i]);
- idst[idint[i]]=i;
- }
- sc(nPath);
- while(nPath--){
- string u,v;
- float w;
- cin >> u >> v;
- scanf("%f",&w);
- g[idst[u]][idst[v]] = min( g[idst[u]][idst[v]], w*2 );
- g[idst[v]][idst[u]] = min( g[idst[u]][idst[v]], w*2 );
- }
- Setpay(nStation);
- floyd_warshall(nStation);
- sc(nQuery);
- if(T) nl;
- printf("Map #%d\n",++T);
- int Query=0;
- while(nQuery--){
- string U,V;
- float w;
- cin >> U >> V;
- scanf("%f",&w);
- float r=g[idst[U]][idst[V]]+paid[idst[U]];
- r += (r*10)/100;
- r /= w;
- printf("Query #%d\n",++Query);
- printPath(idst[U],idst[V]);
- printf("Each passenger has to pay : %.2f taka\n",r);
- }
- idint.clear();
- idst.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement