10356 - Rough Roads

[Noim]

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 ).

[Larry]

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

[Larry]

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]

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]

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]

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]

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]

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]

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]

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

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

[JohnsonWang]

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;
}

[mahade hasan]

cutttttt------>>>
thanx brainfry

[brianfry713]

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

[Neo_1234]

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]

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