#include <stdlib.h> #include <stdio.h> #include <iostream.h> char path1[200]; char path2[200]; int path[200]; bool hover[200]; int route[200]; int bestr[200]; float best; int bestd; bool find(int d, int dmax, float l, char a, bool h, char g, int n) { int i; float l2; bool found=false; bool found2; if (a==g) { if (h) l+=7.0; if (l<best) { best=l; for (i=0; i<=d; i++) bestr[i]=route[i]; bestd=d; } return true; } if (d==dmax) return false; for (i=0; i<n; i++) { if (path1[i]==a) { route[d]=i; l2=l+((float)(path[i]))/(hover[i] ? 9.0 : 5.0); if (h!=hover[i]) l2+=7.0; found2=find(d+1, dmax, l2, path2[i], hover[i], g, n); found=found2||found; } } return found; } void main() { int d, m, n, p, i, j, k,l; char a,b,c; cin>>d; for(i=1; i<=d; i++) { cout<<"Data set "<<i<<":\n\r"; cin>>m>>n>>p; for (j=0; j<n; j++) { cin>>path1[j]>>path2[j]>>path[j]>>c; hover[j]=(c=='H'); n++;j++; path1[j]=path2[j-1]; path2[j]=path1[j-1]; path[j]=path[j-1]; hover[j]=hover[j-1]; if (hover[j]) { n++; j++; hover[j]=false; path1[j]=path1[j-1]; path2[j]=path2[j-1]; path[j]=path[j-1]; n++;j++; hover[j]=false; path1[j]=path2[j-1]; path2[j]=path1[j-1]; path[j]=path[j-1]; } } for (j=1; j<=p; j++) { cout<<"Route "<<j<<":\n\r"; cin>>a>>b; k=10; best=1000000.0; while (!find(0,k,0,a,false,b,n)) { k+=5; } find(0,k+2,0,a,false,b,n); for (l=0; l<bestd; l++) { cout<<" "<<path1[bestr[l]]<<" "<<path2[bestr[l]]<<" "; if (hover[bestr[l]]) cout<<"riding\n\r"; else cout<<"walking\n\r"; } cout<<"Total time "; printf("%.1f seconds\n\r", best); } } }