## 11047 - The Scrooge Co Problem

Moderator: Board moderators

guilhermedelima
New poster
Posts: 1
Joined: Tue Aug 05, 2014 2:30 am

### Re: 11047 - The Scrooge Co Problem

Is it possible to solve with dijkstra? I always get WA.

Could someone help me to find where the bug is? I tried all the test cases of the previous posts, but all of them passed.

Here is the code. Thanks

Code: Select all

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <limits.h>

#define MAX_VERTEX 99

using namespace std;

struct edge{
int neighbor;
int weight;
edge(int n, int w) : neighbor(n), weight(w){
}
};

struct vertex{
int selfDistance;
string name;
};

struct dijkstra_node{
int index;
int distance;
dijkstra_node(int i, int d) : index(i), distance(d){
}
bool operator < (const dijkstra_node& b) const{
return this->distance > b.distance;
}
};

void dijkstra(vertex *graph, int size, int source, int target, string& name);

int main(void){

int C, N, R, v;
string name, sourceName, targetName;
vertex graph[MAX_VERTEX];

cin >> C;

for(int k=0; k<C; k++){

map<string, int> dic;

cin >> N;

for(int i=0; i<N; i++){
cin >> graph[i].name;

dic[ graph[i].name ] = i;
}

for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin >> v;

if( i==j )
graph[i].selfDistance = v;
else if( v>=0 )
}
}

cin >> R;

for(int i=0; i<R; i++){
cin >> name >> sourceName >> targetName;
dijkstra(graph, N, dic[sourceName], dic[targetName], name);
}
}

return 0;
}

void dijkstra(vertex *graph, int size, int source, int target, string& name){

bool visitedArray[MAX_VERTEX] = {0};
long distanceArray[MAX_VERTEX];
int prev[MAX_VERTEX];
priority_queue<dijkstra_node> queue;
int index, cost, neighbor, neighborCost;
vector<string> paths;

for(int i=0; i<size; i++){
distanceArray[i] = LONG_MAX;
prev[i] = -1;
}

if( source != target ){

distanceArray[source] = 0;
queue.push( dijkstra_node(source, 0) );

}else{
if( graph[source].selfDistance >= 0 ){
distanceArray[source] = graph[source].selfDistance;
queue.push( dijkstra_node(source, distanceArray[source]) );
}

prev[neighbor] = source;
distanceArray[neighbor] = neighborCost;
queue.push( dijkstra_node(neighbor, distanceArray[neighbor]) );
}
}

prev[source] = source;

while( !queue.empty() && !visitedArray[target] ){

index = (queue.top()).index;
cost = (queue.top()).distance;

queue.pop();

if( !visitedArray[index] ){

visitedArray[index] = true;

if( !visitedArray[neighbor] && distanceArray[neighbor] > cost + neighborCost ){
prev[neighbor] = index;
distanceArray[neighbor] = cost + neighborCost;
queue.push( dijkstra_node(neighbor, distanceArray[neighbor]) );
}
}
}
}

if( distanceArray[target] == LONG_MAX ){
cout << "Sorry Mr " << name << " you can not go from " << graph[source].name << " to " << graph[target].name << endl;
}else{

cout << "Mr " << name << " to go from " << graph[source].name << " to " << graph[target].name;
cout << ", you will receive " << distanceArray[target] << " euros" << endl;
cout << "Path:";

paths.push_back( graph[target].name );

for(int p=prev[target]; p != source; p=prev[p]){
paths.push_back( graph[p].name );
}

paths.push_back( graph[source].name );

for(unsigned int i=0; i<paths.size(); i++){
cout << (i ? " " : "") << paths[paths.size()-1 - i];
}

cout << endl;
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11047 - The Scrooge Co Problem

This problem should have a special judge or a different input.
I got AC using the Floyd–Warshall algorithm, but WA using Dijkstra's algorithm or DFS.
In the judge's input there are multiple minimum cost paths to get from the source to destination, but only the path found with the Floyd–Warshall algorithm will get AC.
Check input and AC output for thousands of problems on uDebug!