Here's an implementation of dijkstra's algo for CHICAGO.
Full of data structures for optimization. when it gave me correct answers for the test cases, I was very proud. Although nothing is beautiful about this, it apperaed very optmized for the thing it was to do. Unitl......,TLE
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
bool map[105][105];
typedef struct node{
int number;
double min_cost;
}vertex;
typedef struct path{
node from, to;
double cost;
}edge;
bool operator<( edge v1, edge v2){
return v1.cost < v2.cost;
}
double doDijkstra( vertex &from, vertex &to, vector<edge> &G){
priority_queue<edge> PQ;
int dummy;
for( int i = 0; i<G.size(); i++)
if(G[i].from.number == from.number ){
map[G[i].from.number][G[i].to.number] = true;
map[G[i].to.number][G[i].from.number] = true;
G[i].to.min_cost = 1.0*G[i].cost;
PQ.push(G[i]);
}
while( !PQ.empty()){
edge e = PQ.top(); PQ.pop();
if( e.to.number == to.number)
return e.to.min_cost;
for( int i = 0; i<G.size(); i++)
if(G[i].from.number == e.to.number && !map[G[i].from.number][G[i].to.number]){
map[G[i].from.number][G[i].to.number] = true;
map[G[i].to.number][G[i].from.number] = true;
G[i].to.min_cost = e.to.min_cost*G[i].cost;
PQ.push(G[i]);
}
}
return 0.0;
}
int main(){
int n, con, cost;
edge E;
vector<edge> G;
while( true ){
scanf("%d", &n);
if( n == 0)
break;
for( int i=0; i<=n; i++)
memset( map[i], false, sizeof(map));
scanf("%d", &con);
for( int i = 0; i< con; i++){
scanf("%d %d %d", &E.from, &E.to, &cost);
E.cost = ((double)cost)/100.00;
G.push_back(E), swap( E.from, E.to), G.push_back(E);
}
vertex from ,to;
from.number = 1, to.number = n;
printf("%.6lf percent\n", doDijkstra(from, to, G)*100.00);
}
return 0;
}
And then, I did this.., Floyd-Warshall, totally unrequired by the problem. And it solved the problem with time to spare.
#include<iostream>
using namespace std;
double map[105][105];
int main(){
int n, con, cost, from, to;
while( true ){
scanf("%d", &n);
if( n == 0)
break;
scanf("%d", &con);
for( int i = 0; i<= n; i++)
for( int j = 0; j<= n; j++)
map[i][j]=0.0;
for( int i = 0; i< con; i++){
scanf("%d %d %d", &from, &to, &cost);
map[ from ][ to ] = map[ to ][ from ] = ((double)cost)/100.00;
}
for( int k=1; k<=n; k++)
for( int i=1; i<=n; i++)
for( int j=1; j<=n; j++)
map[i][j] = max( map[i][j], map[i][k]*map[k][j]);
printf("%.6lf percent\n", map[1][n]*100.00);
}
return 0;
}
Beautiful that code. But hey, I am not here to discuss on the beauty of the code.
Can ANYONE tell me why the first code failed to reach the time limit??
I cannot sleep properly until I find out... please please please.... Thanx a lot