11710 - Expensive subway

[poixp]

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]

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]

this is a straight forward mst problem. but i think from your algo that you are using bfs.try with kruskal or prim.

[sreejond]

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]

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

[anis_cuet016]

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]

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.

[zobayer]

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

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.

[nymo]

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

[Shafaet_du]

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]

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]

http://uva.onlinejudge.org/index.php?op ... &Itemid=31

[mostafiz93]

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]

Thanks BrainFry701 .
I don't Think this case

[brianfry713]

Input:

Code: Select all

1 0
a
a
2 0
a
b
a
0 0

AC output:

Code: Select all

0
Impossible