11710 - Expensive subway

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

Moderator: Board moderators

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

11710 - Expensive subway

Post by poixp » Tue Oct 20, 2009 10:12 am

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.

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

11710 - Expensive subway

Post by poixp » Mon Oct 26, 2009 9:41 pm

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.

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

Re: 11710 - Expensive subway

Post by calicratis19 » Tue Oct 27, 2009 1:52 pm

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

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

Re: 11710 - Expensive subway

Post by sreejond » Sat Feb 20, 2010 11:19 am

I got RE why?
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 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<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;
}

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

WA: 11710 - Expensive subway

Post by Mehadi » Sun Jul 04, 2010 8:32 am

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

Post by anis_cuet016 » Sun Aug 01, 2010 8:24 pm

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

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11710 - Expensive subway

Post by zobayer » Sat Feb 05, 2011 8:26 pm

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
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
Location: CSE-DU, Bangladesh
Contact:

Re: WA: 11710 - Expensive subway

Post by zobayer » Sat Feb 05, 2011 8:34 pm

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

Post by nymo » Thu Feb 24, 2011 5:40 pm

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11710 - Expensive subway

Post by Shafaet_du » Wed May 11, 2011 6:24 pm

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

Post by Jefe » Sat Mar 03, 2012 11:15 pm

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

Post by brianfry713 » Tue Mar 06, 2012 12:41 am

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

Post by mostafiz93 » Fri Aug 31, 2012 11:11 pm

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

Post by sun_kuet » Mon Oct 28, 2013 1:09 pm

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

Post by brianfry713 » Mon Oct 28, 2013 9:21 pm

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!

Post Reply

Return to “Volume 117 (11700-11799)”