11047 - The Scrooge Co Problem

[guilhermedelima]

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]

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.