00001 #include<scil/scil.h>
00002 #include<scil/constraints/atour.h>
00003 #include<scil/constraints/path.h>
00004
00005 #include<LEDA/tuple.h>
00006 #include<LEDA/stream.h>
00007 #include<LEDA/string.h>
00008 #include<fstream.h>
00009
00010 #define MULT 2
00011
00012 using namespace SCIL;
00013 using namespace LEDA;
00014
00015 typedef two_tuple<node, node> prec;
00016
00017 LEDA::string read_next_line(istream& is) {
00018 LEDA::string s="#";
00019 while((!is.eof()) && ((s.head(1)=="#") || (s.length()==0) || (s.head(1)==" "))) {
00020 s.read_line(is);
00021 };
00022 if(is.eof()) s="";
00023 return s;
00024 };
00025
00026
00027 int main(int argc, char** argv) {
00028
00029
00030
00031 ifstream is(argv[1]);
00032
00033 GRAPH<int,int> G;
00034
00035 LEDA::string_istream si(read_next_line(is));
00036 int n,i,j,k,l,m;
00037
00038 si>>n;
00039 LEDA::string Names[n+1];
00040
00041 cout<<n<<" nodes in the graph\n";
00042
00043 for(int i=0; i<n; i++) Names[i]=read_next_line(is);
00044
00045 int C[n+1][n][n];
00046
00047 while(!is.eof()) {
00048 string_istream si(read_next_line(is));
00049 si>>i;
00050 if(!si.eof()) {
00051 si>>j; si>>k;
00052 leda_string ls;
00053 char ch;
00054 ls.read_line(si);
00055 l=0;
00056 for(int in=0; in<ls.length(); in++) {
00057 ch=ls[in];
00058 if(ch==',') l*=MULT;
00059 if(ch=='0') l=10*l ;
00060 if(ch=='1') l=10*l+1;
00061 if(ch=='2') l=10*l+2;
00062 if(ch=='3') l=10*l+3;
00063 if(ch=='4') l=10*l+4;
00064 if(ch=='5') l=10*l+5;
00065 if(ch=='6') l=10*l+6;
00066 if(ch=='7') l=10*l+7;
00067 if(ch=='8') l=10*l+8;
00068 if(ch=='9') l=10*l+9;
00069 }
00070 if(i!=-1)
00071 C[i][j][k]=l;
00072 else
00073 C[n][j][k]=l;
00074 }
00075 };
00076
00077 ifstream is1(argv[2]);
00078
00079 is1>>k;
00080
00081 is1>>l;
00082 is1>>l;
00083
00084 m=-1;l=n;
00085
00086 list<int> L;
00087 int c1=0,c2=0;
00088
00089 for(int i=0; i<=n; i++) {
00090 is1>>j; j=(j-2)/(2*n);
00091 L.append(j);
00092 if((m!=-1) && (l!=n) && (j!=n)) c1+=C[m][l][j];
00093 m=l; l=j;
00094 for(int j=1; j<2*n; j++) is1>>k;
00095 };
00096
00097 m=-1;l=n;
00098 forall_rev(j, L) {
00099 if((m!=-1) && (l!=n) && (j!=n)) c2+=C[m][l][j];
00100 m=l; l=j;
00101 };
00102
00103 cout<<c1<<" "<<c2<<endl;
00104
00105 m=-1;l=n; int d=0;
00106 if(c1<c2) {
00107 forall(j,L) {
00108 if(m!=-1) { d+=C[m][l][j]; cout<<C[m][l][j]<<" cost\n"; }
00109 m=l; l=j;
00110 cout<<j<<" "<<Names[j]<<endl;
00111 }
00112 } else {
00113 forall_rev(j,L) {
00114 if(m!=-1) { d+=C[m][l][j]; cout<<C[m][l][j]<<" cost\n"; }
00115 m=l; l=j;
00116 cout<<j<<" "<<Names[j]<<endl;
00117 }
00118 }
00119 cout<<d<<" total cost\n";
00120
00121 return (int) (d+0.5);
00122 };
