Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 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 ).
__nOi.m....

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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:
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

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
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
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
``````

thnx for reading it. mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
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:
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

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]; // 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 = 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
Contact:

### Re: 10356 - Rough Roads

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.
Heal The World

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

### Re: 10356 - Rough Roads

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();
{
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 > >();
distances.clear();
}

return 0;
}``````

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10356 - Rough Roads

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

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

got wa 8 times 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)
{

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

}

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

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

for(int i=0;i<sz;i++)
{

//if v is not destination and if he came via cycle
if (v!=node_numb-1 && flag && dist[v] > dist[u][flag]+weight)
{
dist[v]=dist[u][flag]+weight;
q.push(node(v,0,dist[v]));
}
//if he came by carrying cycle on his back , he can now ride
if (!flag && dist[v]>dist[u][flag]+weight)
{
dist[v]=dist[u][flag]+weight;
q.push(node(v,1,dist[v]));
}
}
}
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

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!