10356 - Rough Roads

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

Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Thu Jun 12, 2003 4:34 am

hi shojib,
But as far as I know in dijkstra's algorithm
a vertex is explored only once.
yes shojib, you are right. But you can consider 2 sortest path for every vertex.

There is another way to solve this problem , for which you have to change adjency matrix. ( actually , i don't know that algorithm :cry: ).
__nOi.m....

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Mar 08, 2004 5:46 am

Can someone post some crucial output? I've been having trouble with this. My algorithm was dijkstra..

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Mar 08, 2004 5:51 am

Nevermind.. there are inputs like this in the judge:

3 5
0 1 5
0 1 10
0 1 15
0 1 20
1 2 5

Multiple roads connecting two junctions...

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

Post by rmotome » Sun Jul 09, 2006 1:19 am

I also took care of:
4 4
0 1 10
1 2 5
1 2 0
2 3 15

Vertices 1 & 2 are the same; the edge of length 5 from 1 to 2 is a selfloop. Thus the path from 0 to 3 is even.

I am looking for more critical input

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sat Jul 15, 2006 5:12 pm

What will be the output for the following input:

Code: Select all

4 5
0 1 10
0 2 60
1 2 10
2 3 10
0 4 10
please reply me.

thnx for reading it.:)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jul 15, 2006 9:18 pm

That's not a valid test case.

But for the following input I get 90.

Code: Select all

5 5
0 1 10
0 2 60
1 2 10
2 3 10
0 4 10

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sat Jul 15, 2006 10:01 pm

Thnx mf and sorry it will be 5 5:D.

Hi mf,
Can you explain me how to implement this Input?? Because i am not able
to code this one. I run dijkstra but fail here. Coz is it possible to visit same vertex twice?? We are always finding in dijkstra a optimal path.
So...

please explain me or any kind of help from anybody.

thnx
rabbi

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jul 15, 2006 10:38 pm

Vertices of your graph should be pairs (junction, should your ride or carry bike on the next step), and not just junctions. Then you'll be able to use Dijkstra algorithm.

akercito
New poster
Posts: 3
Joined: Wed Nov 08, 2006 12:11 am
Location: Mexico

Re: 10356 - Rough Roads

Post by akercito » Thu Sep 18, 2008 7:30 am

So far I Have tested all the cases in this forum. I implemented Djikstra algorithm (taking into account each node twice).

Does someone has any critical input or find an error in my code?

Code: Select all

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 1000;

int G[MAX][MAX];
bool visited[MAX][2]; // second dimension for riding or not riding bike. 1 means bike, 0 means no bike


int main () {

	int vertices, edges, s ,d, c, cases = 1;
	while (cin >> vertices >> edges) {
		memset(G, -1, sizeof(G));
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < edges; ++i) {
			cin >> s >> d >> c;
			if (G[s][d] == -1) {
				G[s][d] = G[d][s] = c;
			}
			else {
				G[s][d] = min(G[s][d], c);
				G[d][s] = G[s][d];
			}

		}
		priority_queue<pair<int, pair<int, bool> > > dj; // value, vertex, bike or not bike
		dj.push(make_pair(0, make_pair(0, true)));
		visited[0][1] = true;
		int res = (1 << 30);
		while (!dj.empty()) {
			pair<int, pair<int, bool> > tmp = dj.top();
			dj.pop();
			if (tmp.second.first == vertices - 1 && tmp.second.second == true) {
				res = tmp.first * -1;
				break;
			}
			for (int i = 0; i < vertices; ++i) {
				if (G[tmp.second.first][i] != -1 && visited[i][!tmp.second.second] == false) {
					visited[i][!tmp.second.second] = true;
					dj.push(make_pair(tmp.first + (-1 * G[tmp.second.first][i]), make_pair(i, !tmp.second.second)));
				}
			}
		}
		printf("Set #%d\n", cases++);
		if (res != (1 << 30)) printf("%d\n", res);
		else printf("?\n");
	}
	return 0;

}
thanks a lot!
=)

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 10356 - Rough Roads

Post by calicratis19 » Mon Nov 02, 2009 12:34 pm

i couldn't help writing something about this problem. everyone here seems to have used dijkstra for this problem. but i used floyd warshell :D :D . and guess what , my time limit was 3.564 sec :lol: . i think i have the worst limit :P :P .this my worst time limit in any problem :lol:

but with warshell its so much simpler i think. so if you don't care the time limit :wink: :wink: then i recommend warshell for this problem.
Heal The World

JohnsonWang
New poster
Posts: 4
Joined: Wed May 11, 2011 6:14 am

Re: 10356 - Rough Roads

Post by JohnsonWang » Fri Jul 08, 2011 5:30 am

Hi,

I'm having a similar issue. I'm not sure where exactly my logic is flawed, but, I have a feeling that it is flawed in a few areas. I read over the previous posts, and tried implementing a 'standard' Dijkstra's style solution, however, I am getting wacky results...any feedback would be much appreciated!

Code: Select all

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int INFINITY = 9e8;

// First, compare based on the cost of getting to each node
// Next, compare based on the location of each node
// Finally, compare based on the 'riding the bike' state
bool operator<( const pair < pair <int, int>, bool>& p1, const pair < pair <int, int>, bool>& p2 )
{
	if( p1.first.first != p2.first.first ) return p1.first.first < p2.first.first;
	if( p1.first.second != p2.first.second ) return p1.first.second < p2.first.second;
	return p1.second < p2.second;
}

int main()
{
	int test_case_number = 1, num_nodes, number_edges;
	while( cin >> num_nodes >> number_edges )
	{
		int starting_node = 0, ending_node = num_nodes - 1;

		pair <int, int> temp_pair;
		vector < pair <int, int > > temp_vector_of_pairs( 0, temp_pair );
		vector < vector < pair <int, int> > > adj_list( num_nodes, temp_vector_of_pairs );

		int from, to, cost;
		for( int edge_number = 0; edge_number < number_edges; edge_number++ )
		{
			cin >> from >> to >> cost;
			adj_list[from].push_back( make_pair( to, cost ) );
		}

		// Distance from the starting node to every other node
		// The second parameter represents whether or not Shoan is 'riding the bike' (true = riding the bike, false = walking)
		vector <int> tmp_distance_column( 2, INFINITY );
		vector < vector <int> > distances( num_nodes, tmp_distance_column );
		distances[starting_node][false] = 0;

		// I am not really sure of the correct way to use this:
		// priority_queue < pair < pair <int, int>, bool >, vector < pair < pair <int, int>, bool > >, greater < pair < pair <int, int>, bool > > > pq;

		priority_queue < pair < pair <int, int>, bool > > pq;
		pq.push( make_pair( make_pair( 0, starting_node ), false ) );

		// Here, I am trying to use the standard-ish way of implementing Dijkstra's
		// This is heavily sampled from the Topcoder Algorithm Tutorial "STL Part 2"
		while( !pq.empty() )
		{
			int vertex1 = pq.top().first.second, distance1 = pq.top().first.first;
			bool riding_bike = pq.top().second;
			pq.pop();

			if( vertex1 == ending_node ) break;
			if( distance1 <= distances[vertex1][riding_bike] )
			{
				vector < pair <int, int> >::iterator it = adj_list[vertex1].begin();
				while( it != adj_list[vertex1].end() )
				{
					int vertex2 = it->first, distance2= it->second;
					if( distances[vertex2][!riding_bike] > distances[vertex1][riding_bike] + distance2 )
					{
						distances[vertex2][!riding_bike] = distances[vertex1][riding_bike] + distance2;
						pq.push( make_pair( make_pair( distances[vertex2][!riding_bike], vertex2), !riding_bike) );
					}
					it++;
				}
			}
		}

		cout << "Set #" << test_case_number << endl;
		if( distances[ending_node][true] == INFINITY ) cout << "?" << endl;
		else cout << distances[ending_node][true] << endl;

		test_case_number++;
		pq = priority_queue < pair < pair <int, int>, bool > >();
		adj_list.clear();
		distances.clear();
	}

	return 0;
}

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10356 - Rough Roads

Post by mahade hasan » Thu May 30, 2013 9:46 pm

cutttttt------>>>
thanx brainfry
Last edited by mahade hasan on Fri Jun 14, 2013 6:39 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

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

Re: 10356 - Rough Roads

Post by brianfry713 » Wed Jun 12, 2013 1:55 am

Input:

Code: Select all

4 4
0 1 1
1 2 1
0 2 10
2 3 1
AC output:

Code: Select all

Set #1
11
Check input and AC output for thousands of problems on uDebug!

Neo_1234
New poster
Posts: 3
Joined: Sat Jan 11, 2014 2:43 pm

Re: 10356 - Rough Roads

Post by Neo_1234 » Fri Nov 28, 2014 4:55 pm

got wa 8 times :(

someone please help !

my approach:
i attach one extra information(in my code "flag") to every node : how it get into this node?
if flag is 1 then he came via cycle if 0 then he came by carrying cycle on his back..
then i run dijkstra algorithm..
i check all test cases i found and my code passed .but i kept getting wa.

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

using namespace std;
typedef long long   lli;
typedef pair<int,int> mypair;

#define memSet(a,val) memset(a,val,sizeof(a))
#define inf 1<<28
#define maxm 202

struct node
{
    int u,flag,w;
    node(int a,int b,int c)
    {
        u=a;
        flag=b;
        w=c;
    }

    bool operator < (const node& p) const
    {
        return w>p.w;
    }
};

int main()
{
    int node_numb,edge_numb;
    int caseno=1;
    //freopen("input.txt","r",stdin);

    while(scanf("%d%d",&node_numb,&edge_numb)==2)
    {

        vector<mypair> adjList[node_numb+2];

        while(edge_numb--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);

            adjList[u].push_back(make_pair(v,w));
            adjList[v].push_back(make_pair(u,w));
        }

        priority_queue<node> q;
        int dist[node_numb+2][3];
        memSet(dist,63);

        dist[0][2]=0; //for source , flag is 2
        q.push(node(0,2,0));
        int ans=-1;

        while(!q.empty())
        {
            node top=q.top(); q.pop();

            int u=top.u;
            int flag=top.flag;
            int w=top.w;

            if (u==node_numb-1)
            {
                ans=w;
                break;
            }

            int sz=adjList[u].size();
            for(int i=0;i<sz;i++)
            {
                int v=adjList[u][i].first;
                int weight=adjList[u][i].second;

                //if v is not destination and if he came via cycle
                if (v!=node_numb-1 && flag && dist[v][0] > dist[u][flag]+weight)
                {
                    dist[v][0]=dist[u][flag]+weight;
                    q.push(node(v,0,dist[v][0]));
                }
                //if he came by carrying cycle on his back , he can now ride
                if (!flag && dist[v][1]>dist[u][flag]+weight)
                {
                    dist[v][1]=dist[u][flag]+weight;
                    q.push(node(v,1,dist[v][1]));
                }
            }
        }
        printf("Set #%d\n",caseno++);

        if (ans!=-1)
            printf("%d\n",ans);
        else puts("?");
    }
    return 0;
}

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

Re: 10356 - Rough Roads

Post by brianfry713 » Wed Dec 03, 2014 3:04 am

Input:

Code: Select all

4 4
0 3 10
1 3 10
1 2 10
2 3 10
AC output:

Code: Select all

Set #1
40
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”