11047 - The Scrooge Co Problem

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 11047 - The Scrooge Co Problem

Post by guilhermedelima » Tue Aug 05, 2014 3:01 am

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;
 	vector<edge> adjacencyList;
};
 
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;
 	 	 	graph[i].adjacencyList.clear();
 
 	 	 	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 )
 	 	 	 	 	graph[i].adjacencyList.push_back( edge(j, v) );
 	 	 	}
 	 	}
 
 	 	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]) );
		}

		for(unsigned int i=0; i<graph[source].adjacencyList.size(); i++){
			neighbor = graph[source].adjacencyList[i].neighbor;
			neighborCost = graph[source].adjacencyList[i].weight;
			
			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;
 
 	 	 	for(unsigned int i=0; i<graph[index].adjacencyList.size(); i++){
 	 	 	 	neighbor = graph[index].adjacencyList[i].neighbor;
 	 	 	 	neighborCost = graph[index].adjacencyList[i].weight;
 
 	 	 	 	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

Post by brianfry713 » Wed Aug 06, 2014 1:23 am

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!

Post Reply

Return to “Volume 110 (11000-11099)”