11710  Expensive subway
Moderator: Board moderators
11710  Expensive subway
There is not a chapter for that problem on forum, i will write it here...
Problem description
http://uva.onlinejudge.org/index.php?op ... oblem=2757
I've tried that problem while CUPCAM 2009 championship but I got WA.
Here is my algorithm:
Read all cities
Sort it(to use binary search)
Now read the connections and build graph
Read the starting city.
We start from one city, and travel cost is zero.
Using priority queue get the city with min travel cost
If city visited goto next
Mark city as visited
Set the min travel cost for that city
 Add to queue cities that have connection with current. The travel cost = current cost + cost of ticket.
After that If there is at least one of city not visited the answer is Impossible
Otherwise the answer is max value of min travel cost for all cities.
Problem description
http://uva.onlinejudge.org/index.php?op ... oblem=2757
I've tried that problem while CUPCAM 2009 championship but I got WA.
Here is my algorithm:
Read all cities
Sort it(to use binary search)
Now read the connections and build graph
Read the starting city.
We start from one city, and travel cost is zero.
Using priority queue get the city with min travel cost
If city visited goto next
Mark city as visited
Set the min travel cost for that city
 Add to queue cities that have connection with current. The travel cost = current cost + cost of ticket.
After that If there is at least one of city not visited the answer is Impossible
Otherwise the answer is max value of min travel cost for all cities.
11710  Expensive subway
I've tried that problem while CUPCAM 2009 championship but I got WA.
Here is my algorithm:
Read all cities
Sort it(to use binary search)
Now read the connections and build graph
Read the starting city.
We start from one city, and travel cost is zero.
Using priority queue get the city with min travel cost
If city visited goto next
Mark city as visited
Set the min travel cost for that city
 Add to queue cities that have connection with current. The travel cost = current cost + cost of ticket.
After that If there is at least one of city not visited the answer is Impossible
Otherwise the answer is max value of min travel cost for all cities.
Here is my algorithm:
Read all cities
Sort it(to use binary search)
Now read the connections and build graph
Read the starting city.
We start from one city, and travel cost is zero.
Using priority queue get the city with min travel cost
If city visited goto next
Mark city as visited
Set the min travel cost for that city
 Add to queue cities that have connection with current. The travel cost = current cost + cost of ticket.
After that If there is at least one of city not visited the answer is Impossible
Otherwise the answer is max value of min travel cost for all cities.

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
Re: 11710  Expensive subway
this is a straight forward mst problem. but i think from your algo that you are using bfs.try with kruskal or prim.
Heal The World
Re: 11710  Expensive subway
I got RE why?
Thnx in advance.
Thnx in advance.
Code: Select all
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <string>
#include <numeric>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
using namespace std;
#define OFF ios::sync_with_stdio(false)
#define IOR(x) freopen(x,"r",stdin);
#define IOW(x) freopen(x,"w",stdout);
#define DEBUG if(0)
#define i64 long long
#define u64 unsigned long long
#define eps 1e10
#define LET(x,p) __typeof(p) x
#define FORIT(it,p) for(__typeof(p.end()) it=p.begin();it!=p.end();it++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ALL(p) p.begin(),p.end()
#define CLR(p) p.clear()
#define REV(p) reverse(All(p))
#define pb(p) push_back(p)
#define pii pair< int, int >
#define mset(p,v) memset(p,v,sizeof(p))
#define UB(p,v) upper_bound(ALL(p),v)
#define LB(p,v) lower_bound(ALL(p),v)
#define MAXN 2000000000
typedef pair<long,long> ii;
vector<vector<long> > adj(402,vector<long>(402,0));
vector<long> deg(402);
vector<vector<long> > cost(402,vector<long>(402,0));
vector<long> distanc(402);
map<string,long> M;
string str,str1,str2;
long c,V,E,cnt;
long Prim(long start)
{
long dist,i,cst=0;
ii top;
distanc[start]=0;
priority_queue<ii,vector<ii>,greater<ii> > Q;
Q.push(ii(0,start));
cnt=0;
while(!Q.empty())
{
top=Q.top();
Q.pop();
start=top.second;
dist=top.first;
if(dist<=distanc[start])
{
cnt++;
for(i=1;i<=deg[start];i++)
{
if(distanc[adj[start][i]] > cost[start][i])
{
distanc[adj[start][i]] = cost[start][i];
Q.push(ii(distanc[adj[start][i]],adj[start][i]));
}
}
}
}
for(i=1;i<=V;i++)
cst+=distanc[i];
return cst;
}
void Ini()
{
long i;
for(i=0;i<=V;i++)
distanc[i]=MAXN;
}
int main()
{
long i,n,c,cst,st;
while(cin>>V>>E)
{
if(!V&&!E) break;
n=1;
for(i=0;i<V;i++)
{
cin>>str;
M[str]=n++;
}
for(i=0;i<E;i++)
{
cin>>str1>>str2>>c;
deg[M[str1]]++;
deg[M[str2]]++;
adj[M[str1]][deg[M[str1]]]=M[str2];
adj[M[str2]][deg[M[str2]]]=M[str1];
cost[M[str1]][deg[M[str1]]]=c;
cost[M[str2]][deg[M[str2]]]=c;
}
cin>>str;
st=M[str];
Ini();
cst=Prim(st);
if(cnt==V)
cout<<cst<<endl;
else
cout<<"Impossible\n";
M.clear();
deg.clear();
}
return 0;
}
WA: 11710  Expensive subway
I simply do mst then if reachable from the given station sum up it. if anyone not reachable then impossible.If am wrong can anybody help me. Here is my code:
Code: Select all
Code Removed
Last edited by Mehadi on Thu Feb 19, 2015 9:02 am, edited 1 time in total.

 New poster
 Posts: 15
 Joined: Thu Jul 08, 2010 8:28 am
Re: 11710  Expensive subway
Mehadi ...
I guess this forum is not about posting the code, it is about just sharing ur views and ideas, ur bugs ........ please remove the code, and giver other the opportunity of thinking ........ rather then just copying ......
Anis
I guess this forum is not about posting the code, it is about just sharing ur views and ideas, ur bugs ........ please remove the code, and giver other the opportunity of thinking ........ rather then just copying ......
Anis

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11710  Expensive subway
Probably you are new here.... You can post your code here if it is not a correct one, and you are not able to find the bug yourself.anis_cuet016 wrote:Mehadi ...
I guess this forum is not about posting the code, it is about just sharing ur views and ideas, ur bugs ........ please remove the code, and giver other the opportunity of thinking ........ rather then just copying ......
Anis
You should not always say what you know, but you should always know what you say.

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: WA: 11710  Expensive subway
This line does not work as you might have expected:Mehadi wrote:I simply do mst then if reachable from the given station sum up it. if anyone not reachable then impossible.If am wrong can anybody help me. Here is my code:Code: Select all
Code: Select all
while(scanf("%ld%ld",&N,&M),N!=0,M!=0)
You should not always say what you know, but you should always know what you say.
Re: 11710  Expensive subway
For no. of stations, s = 1 and no. of connections, c = 0; you have to output 0.
regards,
nymo
nymo

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 11710  Expensive subway
Just find the mst and check if the graph is connected. Data set is quite large i guess(my code surprisingly needs more than 1 sec!),so don't use union find separately to check connectivity. Run kruskal and check if there are n1 edges in the mst.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 11710  Expensive subway
Hello,
I'm trying to do the following:
 I note that the graph is disconnected, I print "Impossible."
 If the graph is connected then run Kruskal's algorithm, using Find Union, for all test cases, and I thought that my generator cases could create my program works properly, but I'm getting Runtime Error.
I already checked the size of the vectors.
Does anyone have any idea what might be?
Thank's
I'm trying to do the following:
 I note that the graph is disconnected, I print "Impossible."
 If the graph is connected then run Kruskal's algorithm, using Find Union, for all test cases, and I thought that my generator cases could create my program works properly, but I'm getting Runtime Error.
I already checked the size of the vectors.
Does anyone have any idea what might be?
Thank's

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11710  Expensive subway
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 31
 Joined: Thu Nov 24, 2011 12:08 am
Re: 11710  Expensive subway
The number of connections may be 0.
consider this input:
output is Impossible
consider this input:
Code: Select all
2 0
a
b
a
0 0
11710  Expensive subway
Thanks BrainFry701 .
I don't Think this case
I don't Think this case
Last edited by sun_kuet on Mon Oct 28, 2013 11:06 pm, edited 1 time in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11710Expensive subway
Input:AC output:
Code: Select all
1 0
a
a
2 0
a
b
a
0 0
Code: Select all
0
Impossible
Check input and AC output for thousands of problems on uDebug!