## 11710 - Expensive subway

Moderator: Board moderators

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

### 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:
-Sort it(to use binary search)
-Now read the connections and build graph
-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.

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

### 11710 - Expensive subway

I've tried that problem while CUPCAM 2009 championship but I got WA.
Here is my algorithm:
-Sort it(to use binary search)
-Now read the connections and build graph
-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.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
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

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 11710 - Expensive subway

I got RE why?

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 1e-10

#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<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++)
{
{
}
}
}
}
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]]++;
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;
}``````

New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

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

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

### Re: 11710 - Expensive subway

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

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 11710 - Expensive subway

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
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.
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: WA: 11710 - Expensive subway

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:
This line does not work as you might have expected:

Code: Select all

``````while(scanf("%ld%ld",&N,&M),N!=0,M!=0)
``````
Note, M can be 0 here, but both M and N can not ! And, comma works almost similar as the && operator.
You should not always say what you know, but you should always know what you say.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Re: 11710 - Expensive subway

For no. of stations, s = 1 and no. of connections, c = 0; you have to output 0.
regards,
nymo

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
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 n-1 edges in the mst.

Jefe
New poster
Posts: 1
Joined: Sat Mar 03, 2012 10:14 pm

### 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

brianfry713
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!

mostafiz93
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:

Code: Select all

``````2 0
a
b
a
0 0``````
output is Impossible

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

### 11710 - Expensive subway

Thanks BrainFry701 .
I don't Think this case
Last edited by sun_kuet on Mon Oct 28, 2013 11:06 pm, edited 1 time in total.

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

### Re: 11710-Expensive subway

Input:

Code: Select all

``````1 0
a
a
2 0
a
b
a
0 0
``````
AC output:

Code: Select all

``````0
Impossible
``````
Check input and AC output for thousands of problems on uDebug!