OJ Board

Posted: **Sun Jun 22, 2014 12:45 pm**

A little modification to the problem. I want print the path along which the guide has to travel. How to do that?

Posted: **Tue Jun 24, 2014 12:04 am**

http://en.wikipedia.org/wiki/Floyd%E2%8 ... nstruction

Posted: **Tue Jul 15, 2014 9:55 pm**

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.

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+((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
                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+((passengers-1) / (carry_count_min[end]-1));
        cout << "Minimum Number of Trips = " << static_cast<long long int>(rounds) << endl << endl;
        
    }
    return 0;
}

Posted: **Wed Jul 16, 2014 8:04 pm**

Try solving it without using floating point.
To take the integer ceiling of a divided by b, you could use:
(a + b - 1) / b

Posted: **Thu Jul 17, 2014 1:19 pm**

Try solving it without using floating point.
To take the integer ceiling of a divided by b, you could use:
(a + b - 1) / b

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.

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->second-1);
				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;
}

Posted: **Thu Jul 17, 2014 9:46 pm**

BFS won't work. Try using the minimax version of Floyd-Warshall's algorithm or a modified Dijkstra's algorithm.

Posted: **Mon Sep 22, 2014 5:08 pm**

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.

Posted: **Tue Sep 23, 2014 12:24 pm**

Maybe it's possible to implement heap to optimize dijkstra's algo from O(N * N) to O(N * logN).

Posted: **Tue Sep 23, 2014 2:38 pm**

Can someone help me by showing my mistake ? I am getting a Runtime Error !

Code: Select all

Acc

Posted: **Tue Sep 23, 2014 7:22 pm**

Try this

turcse143 wrote:check this input:
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
hope it helps.

Posted: **Tue Sep 23, 2014 9:56 pm**

TO: lighted Your test works for my code, it outputs 0. But I am getting a Runtime Error which is really strange.

Posted: **Tue Sep 23, 2014 11:34 pm**

Input

Code: Select all

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.

Posted: **Wed Sep 24, 2014 12:44 am**

But do the real tests have blanks inbetween or not ?

Posted: **Wed Sep 24, 2014 2:42 am**

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.

Posted: **Wed Sep 24, 2014 8:34 am**

Thanks a lot, I got Acc with Scanner.

OJ Board

10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide

Re: 10099 - The Tourist Guide