10099  The Tourist Guide
Moderator: Board moderators
Re: 10099  The Tourist Guide
A little modification to the problem. I want print the path along which the guide has to travel. How to do that?

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10099  The Tourist Guide
Check input and AC output for thousands of problems on uDebug!
Re: 10099  The Tourist Guide
Hi,
Same problem with many others that although my code goes through with all of the test cases I could find and generate, I keep getting WA from the judge. Maybe you can see the problem here and help me.
One comment would be, this code is my playground so I intentionally used dijkstra's shortest path and BFS approach with sticking to STL.
Same problem with many others that although my code goes through with all of the test cases I could find and generate, I keep getting WA from the judge. Maybe you can see the problem here and help me.
One comment would be, this code is my playground so I intentionally used dijkstra's shortest path and BFS approach with sticking to STL.
Code: Select all
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <iomanip>
#include <algorithm>
#include <stdint.h>
#include <exception>
#include <set>
#include <queue>
using namespace std;
struct Pred {
Pred(int i): val(i) {}
bool operator() (std::pair<const std::pair<int, int>, long int> &p) {
return p.first.first == val;
}
private:
int val;
};
int main() {
int N, R;
queue<int> qu;
map<int, bool> visited_cities;
map<int, bool> queued_cities;
map<int, long int> carry_count;
map<int, long int> carry_count_min;
int count = 0;
while(count++, true) {
visited_cities.clear(); queued_cities.clear(); carry_count_min.clear(); carry_count.clear();
cin >> N >> R;
if(N==0 && R==0) break;
for(int i=1; i<=N; ++i) {
visited_cities[i] = false;
queued_cities[i] = false;
carry_count[i] = numeric_limits<int>::max();
carry_count_min[i] = numeric_limits<int>::max();
}
map<pair<int, int>, long int> ways;
int c1, c2, p;
while (R) {
cin >> c1 >> c2 >> p;
ways[{c2, c1}] = p;
ways[{c1, c2}] = p;
}
int start, end, passengers;
cin >> start >> end >> passengers;
qu.push(start);
queued_cities[start] = true;
carry_count[start] = 0;
while(!qu.empty()) {
int working = qu.front(); qu.pop();
if(working == end) continue;
visited_cities[working] = true;
map<pair<int, int>, long int>::iterator it = ways.begin();
while((it = find_if(it, ways.end(), Pred(working)))!= ways.end()) {
if(visited_cities[it>first.second]) {
it++;
continue; // if I visited here previously
}
if(!queued_cities[it>first.second]) { //enqueue city unless it has been previously, not necessarily needed though. already we are mimicking this by visited flag
qu.push(it>first.second);
queued_cities[it>first.second] = true;
}
double rounds = 1+((passengers1) / (it>second1)); //find rounds to make on this road minus 1 is from algorithm, plus 1 is the guide taking this seat
if(rounds > 0 && carry_count[working]+(int)rounds < carry_count[it>first.second]) { //if my working cells carry count plus the roads carry count is smaller than previous carry counts
carry_count[it>first.second] = carry_count[working]+(int)rounds;
carry_count_min[it>first.second] = min(it>second, carry_count_min[working]);
}
it++;
}
}
//cout << carry_count[end] << endl;
cout << "Scenario #" << count << endl;
double rounds;
if(passengers==0) rounds = 0;
else rounds = 1+((passengers1) / (carry_count_min[end]1));
cout << "Minimum Number of Trips = " << static_cast<long long int>(rounds) << endl << endl;
}
return 0;
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10099  The Tourist Guide
Try solving it without using floating point.
To take the integer ceiling of a divided by b, you could use:
(a + b  1) / b
To take the integer ceiling of a divided by b, you could use:
(a + b  1) / b
Check input and AC output for thousands of problems on uDebug!
Re: 10099  The Tourist Guide
I was doing this in different way on the next line but nevertheless I did take your advice and changed the code to the following. Unfortunately again my test cases are fine but it is still a WA according to judge.Try solving it without using floating point.
To take the integer ceiling of a divided by b, you could use:
(a + b  1) / b
Code: Select all
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <iomanip>
#include <algorithm>
#include <stdint.h>
#include <exception>
#include <set>
#include <queue>
using namespace std;
struct Pred {
Pred(int i) : val(i) {}
bool operator() (std::pair<const std::pair<int, int>, long int> &p) {
return p.first.first == val;
}
private:
int val;
};
int main() {
int N, R;
queue<int> qu;
map<int, bool> visited_cities;
map<int, bool> queued_cities;
map<int, long int> carry_count;
map<int, long int> carry_count_min;
int count = 0;
while (count++, true) {
visited_cities.clear(); queued_cities.clear(); carry_count_min.clear(); carry_count.clear();
cin >> N >> R;
if (N == 0 && R == 0) break;
for (int i = 1; i <= N; ++i) {
visited_cities[i] = false;
queued_cities[i] = false;
carry_count[i] = numeric_limits<int>::max();
carry_count_min[i] = numeric_limits<int>::max();
}
map<pair<int, int>, long int> ways;
int c1, c2, p;
while (R) {
cin >> c1 >> c2 >> p;
ways[{c2, c1}] = p;
ways[{c1, c2}] = p;
}
int start, end, passengers;
cin >> start >> end >> passengers;
qu.push(start);
queued_cities[start] = true;
carry_count[start] = 0;
while (!qu.empty()) {
int working = qu.front(); qu.pop();
if (working == end) continue;
visited_cities[working] = true;
map<pair<int, int>, long int>::iterator it = ways.begin();
while ((it = find_if(it, ways.end(), Pred(working))) != ways.end()) {
if (visited_cities[it>first.second]) {
it++;
continue; // if I visited here previously
}
if (!queued_cities[it>first.second]) { //enqueue city unless it has been previously, not necessarily needed though. already we are mimicking this by visited flag
qu.push(it>first.second);
queued_cities[it>first.second] = true;
}
//int rounds = 1 + ((passengers  1) / (it>second  1)); //find rounds to make on this road minus 1 is from algorithm, plus 1 is the guide taking this seat
//(a + b  1) / b
int rounds = (passengers + it>second  1  1) / (it>second1);
if (rounds > 0 && carry_count[working] + rounds < carry_count[it>first.second]) { //if my working cells carry count plus the roads carry count is smaller than previous carry counts
carry_count[it>first.second] = carry_count[working] + (int)rounds;
carry_count_min[it>first.second] = min(it>second, carry_count_min[working]);
}
it++;
}
}
//cout << carry_count[end] << endl;
cout << "Scenario #" << count << endl;
int rounds;
if (passengers == 0) rounds = 0;
//else rounds = 1 + ((passengers  1) / (carry_count_min[end]  1));
else rounds = (passengers + carry_count_min[end]  1  1) / (carry_count_min[end]  1);
cout << "Minimum Number of Trips = " << rounds << endl << endl;
}
return 0;
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10099  The Tourist Guide
BFS won't work. Try using the minimax version of FloydWarshall's algorithm or a modified Dijkstra's algorithm.
Check input and AC output for thousands of problems on uDebug!
Re: 10099  The Tourist Guide
how it is solved in 0.000 sec? can anyone explain???????? My AC code solve in 0.022 sec and i use dijkstra's algo and do not use any stl..........
thanks in Advance.
thanks in Advance.
Re: 10099  The Tourist Guide
Maybe it's possible to implement heap to optimize dijkstra's algo from O(N * N) to O(N * logN).
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 10099  The Tourist Guide
Can someone help me by showing my mistake ? I am getting a Runtime Error !
Code: Select all
Acc
Last edited by sreka11 on Wed Sep 24, 2014 11:26 am, edited 2 times in total.
Re: 10099  The Tourist Guide
Try this
turcse143 wrote:check this input:hope it helps.Code: Select all
input: 7 10 1 2 30 1 3 15 1 4 10 2 4 25 2 5 60 3 4 40 3 6 20 4 7 35 5 7 20 6 7 30 1 1 99 0 0 output: Scenario #1 Minimum Number of Trips = 0
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 10099  The Tourist Guide
TO: lighted Your test works for my code, it outputs 0. But I am getting a Runtime Error which is really strange.
Re: 10099  The Tourist Guide
Input
I joined sample test above and it shows RE here. http://ideone.com/RKyqfb
I am not sure if it is main reason of RE, but when you seperate input tests by a blank line it gives RE.
Code: Select all
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99
0 0
I am not sure if it is main reason of RE, but when you seperate input tests by a blank line it gives RE.
Last edited by lighted on Wed Sep 24, 2014 1:26 am, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 10099  The Tourist Guide
But do the real tests have blanks inbetween or not ?
Re: 10099  The Tourist Guide
I checked accepted solution for 10099 to read by line into cstring and then sscanf from that cstring and got WA. So it becomes that there can be blank lines or some input values that should be on same line can be on different lines. Try to use Scanner with nextInt().
Also i sent you PM.
Also i sent you PM.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 10099  The Tourist Guide
Thanks a lot, I got Acc with Scanner.