OJ Board

The Online Judge board
https://onlinejudge.org/board/

544 - Heavy Cargo

https://onlinejudge.org/board/viewtopic.php?t=2036

Page 2 of 3

Re: 544 - heavy cargo

Posted: Fri Sep 18, 2009 11:50 am
by calicratis19
can anyone please tell me how to solve this problem with mst.i solved it with floyd warshell. but i want to know how to solve with mst. i would prefer kruskel much :D :D .
thank you .


EDIT: solved with kruskal. :D :D

Re: 544 - heavy cargo

Posted: Wed Oct 14, 2009 1:11 pm
by Jehad Uddin
just find a maximum spanning tree and u will get the ans,:D

Re: 544 - heavy cargo

Posted: Sat May 08, 2010 12:54 am
by Bruno
I am doing a maximum spanning tree and then finding the min weight between the source and dest, and its giving me WA :cry: , is this correct?

Re: 544 - heavy cargo

Posted: Mon May 17, 2010 7:45 pm
by calicratis19
Yeah your approach is correct :)

Re: 544 - heavy cargo

Posted: Thu Jun 02, 2011 6:27 pm
by indraep
please help me, I always got WA.

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <map>

using namespace std;

#define REP(i,n) for (int i = 0; i < n; i++)
#define pb push_back
#define mp make_pair
#define CLEAR(m) memset(m, 0, sizeof(m))
#define LL long long

int prim (map <string, vector <pair <string, int> > > adj, string source, string dest) {
	int ans = 2000000;
	int len;
	
	priority_queue <pair<int, string> > pq;
	
	map <string, bool> visit;
	
	pq.push(mp(20000000, source));
	
	string node;
	
	while (!pq.empty()) {
		node = pq.top().second;
		
		if (visit[node])
			pq.pop();
		else {
			visit[node] = 1;
			if (node == dest)
				break;
			len = adj[node].size();
			if (pq.top().first < ans)
				ans = pq.top().first;
			
			REP(i,len) {
				pq.push(mp(adj[node][i].second, adj[node][i].first));
			}
		}
	}
	return ans;
}

int main () {
	int n, r;
	
	string a, b, source, dest;
	int cost;
	
	int id = 1;
	while (scanf("%d %d", &n, &r) != EOF) {
		
		if (n == 0 && r == 0)
			break;
		
		map <string, vector <pair <string, int> > > adj;
		
		REP(i, r) {
			cin >> a >> b;
			scanf("%d", &cost);
			
			adj[a].pb(mp(b, cost));
			adj[b].pb(mp(a, cost));
		}
		
		cin >> source >> dest;
		
		printf("Scenario #%d\n", id++);
		printf("%d tons\n\n", prim(adj, source, dest));
	}
}

Re: 544 - heavy cargo

Posted: Tue Jul 23, 2013 6:27 pm
by shuvokr
I don't understand why i get WA again and again, need help
My code

Code: Select all

//Templet start
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <algorithm>

using namespace std;

#define sf scanf
#define pf printf
#define long long lld
#define llu unsigned long long
#define fo(i, n) for(i = 0; i < n; i++)
#define of(i, n) for(i = n - 1; i >= 0; i--)
#define mem(n, v) memset(n, v, sizeof( n ))
#define eps 1e-8
#define INF 5000
#define pb push_back
#define maxn 200+2

#define white 0
#define black 1

typedef pair<int, int> pii;
typedef  vector<int> vi;
typedef vector<pii> vii;


int diraction1[] = {-1, 0, 0, 1, 1, -1, -1, 1};
int diraction2[] = {0, -1, 1, 0, 1, -1, 1, -1};
int horsed1[] = {-2, -2, -1, 1, 2, 2, 1, -1};
int horsed2[] = {1, -1, -2, -2, -1, 1, 2, 2};

//Templet end
void input();
void reset();
void BFS(int u);

struct data
{
    int u, cost;
    data() {}

    bool operator < (const data& s) const
    {
        return cost < s.cost;
    }
};

int node, edge, parents[ maxn ], cc[ maxn ];
vector <vii> graph;
map <string, int> m;
char s[ 32 ], e[ 32 ];
bool mark[ maxn ];

int main()
{
    input();

    return 0;
}
void input()
{
    int i, j, k, src, end, cst, res, kag = 0;
    while(~sf("%d %d", &node, &edge))
    {
        if(!node && !edge) break;
        k = 1;
        reset();
        // get input
        fo(i, edge)
        {
            mem(s, 0); mem(e, 0);
            sf("%s %s %d", s, e, &cst);
            if(!m[ s ]) m[ s ] = k++;
            if(!m[ e ]) m[ e ] = k++;
            graph[ m[ s ] ].pb( pii(m[ e ], cst) );
            graph[ m[ e ] ].pb( pii(m[ s ], cst) );
        }
        mem(s, 0); mem(e, 0);
        sf("%s %s", s, e);
        //*******************************
        if(m[ s ] == m[ e ])
        {
            pf("Scenario #%d\n0 tons\n\n", ++kag);
            continue;
        }
        BFS( m[ s ] );
        int ss = m[ e ];
        // find the result
        res = cc[ ss ];
        while(true)
        {
            ss = parents[ ss ];
            if(ss == m[ s ])
            {
                break;
            }
            res = min(res, cc[ ss ]);
        }
        //**********************
        pf("Scenario #%d\n%d tons\n\n", ++kag, res);
    }
}
void BFS(int u)
{
    int i, j, tmp, wait;
    priority_queue <data> Q;
    data x;
    x.u = u; x.cost = 0;
    Q.push( x );
    mark[ u ] = false;
    while(!Q.empty())
    {
        x = Q.top(); Q.pop();
        u = x.u;
        wait = x.cost;
        for(i = 0; i < graph[ u ].size(); i++)
        {
            pii pr = graph[ u ][ i ];
            if(mark[ pr.first ])
            {
                parents[ pr.first ] = u;
                cc[ pr.first ] = pr.second; // i use cc[] for save the paths cost
                mark[ pr.first ] = false;
                x.u = pr.first; x.cost = pr.second;
                Q.push( x );
                if(pr.first == m[ e ]) // when i find the end point then stop
                {
                    while(!Q.empty()) Q.pop();
                    i = graph[ u ].size();
                }
            }
        }
    }
}
void reset()
{
    m.clear();
    graph.assign(node+1, vii());
    int i;
    for(i = 1; i <= node; i++)
    {
        parents[ i ] = -1;
        mark[ i ] = true;
        cc[ i ] = -1;
    }
    mark[ 0 ] = true;
}

Re: 544 - heavy cargo

Posted: Wed Jul 24, 2013 12:54 am
by brianfry713
From uhunt:
AKJ88> ovuhS, See i/0 #2 I've sent for you here: http://ideone.com/ykUSR9 Ac output for Scenario #3 is 4 not 2.

Re: 544 - heavy cargo

Posted: Sun Oct 27, 2013 10:54 pm
by triplemzim
problem id: 544 , heavy cargo

why getting TLE... please help:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>


using namespace std;




class data
{
	public:
		int u,e,cst;
	bool operator<(const data &p)const { return cst<p.cst;}
};

vector<int>v[210];
int cost[210][210];
char store[210][35];
int n,r;
int parent[210];
bool color[210];
void prim(int src,int target)
{
//	memset(parent,0,sizeof(parent));
	memset(color,true,sizeof(color));
	priority_queue<data> q;
//	cout<<src<<" "<<target<<endl;
	data temp,current;
	vector<int>vnew;
	int top=src,a;
	color[src]=false;
	vnew.push_back(src);
	while(vnew.size()!=n)
	{

		for(int i=0;i<v[top].size();i++)
		{	a=v[top][i];
			if(color[a]==true)
			{
//				cout<<"Pushed: "<<top<<" "<<v[top][i]<<endl;
				temp.u=top;

				temp.e=a;

				temp.cst=cost[top][a];
				q.push(temp);
			}
		}
//		if(q.empty()) break;

		current=q.top();

		vnew.push_back(current.e);

		parent[current.e]=current.u;
		if(current.e==target) break;

		color[current.e]=false;
//		cout<<current.u<<" >> "<< current.e<<endl;
		top=current.e;
		q.pop();
	}


	return;


}


int main()
{
	map<string,int> m;


   int src,target,pos1,pos2,len,d,temp,caseno=1;
   char c[35];


   bool flag=false;
    while(scanf("%d%d",&n,&r)==2)
    {
        if(n==0 && r==0)
            break;
        len=1;
        flag=false;
        for(int i=0;i<r;i++)
        {
            scanf("%s",c);
            if(m[c]) pos1=m[c];
            else pos1=m[c]=len++;

            scanf("%s",c);
            if(m[c]) pos2=m[c];
            else pos2=m[c]=len++;

            v[pos1].push_back(pos2);
            v[pos2].push_back(pos1);
            scanf("%d",&d);
            cost[pos1][pos2]=d;
            cost[pos2][pos1]=d;
        }

        scanf("%s",c);
		src=m[c];

		scanf("%s",c);
        target=m[c];

        prim(src,target);
        int temp_cost=100000;
        while(target!=src)
        {
//			cout<<target<<endl;
			temp=cost[target][parent[target]];
			if(temp_cost>temp) temp_cost=temp;
			target=parent[target];
		}
		printf("Scenario #%d\n%d tons\n\n",caseno++,temp_cost);

		memset(v,0,sizeof(v));
		m.clear();

    }
    return 0;

}

Re: 544 - heavy cargo

Posted: Mon Oct 28, 2013 9:32 pm
by brianfry713

Code: Select all

vector<int>v[210];
...
v[pos1].push_back(pos2);
v[pos2].push_back(pos1);
...
memset(v,0,sizeof(v));
Instead of memset, try something like:

Code: Select all

for(int i = 1; i <= n; i++)
  v[i].clear();

Re: 544 - heavy cargo

Posted: Tue Oct 29, 2013 12:02 pm
by triplemzim
still TLE... :( here is my updated code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>


using namespace std;




struct data
{

		int u,e,cst;
	bool operator<(const data &p)const { return cst<p.cst;}
};

vector<int>v[210];
int cost[210][210];
char store[210][35];
int n,r;
int parent[210];
bool color[210];
void prim(int src,int target)
{

	memset(color,true,sizeof(color));
	priority_queue<data> q;

	data temp,current;
	vector<int>vnew;
	int top=src,a;
	color[src]=false;
	int count=1;
	while(count!=n)
	{

		for(int i=0;i<v[top].size();i++)
		{	a=v[top][i];
			if(color[a]==true)
			{

				temp.u=top;

				temp.e=a;

				temp.cst=cost[top][a];
				q.push(temp);
			}
		}


		current=q.top();
		a=current.e;
		count++;

		parent[a]=current.u;
		if(a==target) break;

		color[a]=false;

		top=a;
		q.pop();
	}


	return;


}


int main()
{
	map<string,int> m;


   int src,target,pos1,pos2,len,d,temp,caseno=1;
   char c[35];


   bool flag=false;
    while(scanf("%d%d",&n,&r)==2)
    {
        if(n==0 && r==0)
            break;
        len=1;
        flag=false;
        for(int i=0;i<r;i++)
        {
            scanf("%s",c);
            if(m[c]) pos1=m[c];
            else pos1=m[c]=len++;

            scanf("%s",c);
            if(m[c]) pos2=m[c];
            else pos2=m[c]=len++;

            v[pos1].push_back(pos2);
            v[pos2].push_back(pos1);
            scanf("%d",&d);
            cost[pos1][pos2]=d;
            cost[pos2][pos1]=d;
        }

        scanf("%s",c);
		src=m[c];

		scanf("%s",c);
        target=m[c];

        prim(src,target);
        int temp_cost=100000;
        while(target!=src)
        {

			temp=cost[target][parent[target]];
			if(temp_cost>temp) temp_cost=temp;
			target=parent[target];
		}
		temp_cost!=100000 ? printf("Scenario #%d\n%d tons\n\n",caseno++,temp_cost) : printf("Scenario #%d\n0 tons\n\n",caseno++);

		for(int i = 1; i <= len; i++)
			v[i].clear();
		m.clear();

    }
    return 0;

}

Re: 544 - heavy cargo

Posted: Wed Oct 30, 2013 1:16 am
by brianfry713
That is not a correct implementation of http://en.wikipedia.org/wiki/Prim%27s_algorithm
Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not

Try input:

Code: Select all

4 4
a b 2
b c 2
c a 2
c d 1
a d
0 0

Re: 544 - heavy cargo

Posted: Sat Nov 02, 2013 12:03 am
by triplemzim
thanks... brainfry... got AC...

544 heavy cargo

Posted: Sun Jan 19, 2014 3:34 pm
by bitaron
Need some critical test cases ??

Re: 544 - heavy cargo

Posted: Tue Mar 25, 2014 7:59 pm
by killerwife
Hello, I used the bellman ford modified to find minimal weight instead of full weight. I cant find a critical test case that gives me WA, all the other cases ive found on the internet are correct. Pls help.

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

 


public class Main{
public static int min(int a, int b)
{
    if(a>b)
        {
        return b;
    }
    else
        {
        return a;
    }
}
    
    public static void main(String[] args){
       try{
       BufferedReader citac=new BufferedReader(new InputStreamReader(System.in));
       int pocetmiest,pocetciest;
       String []mesta=new String[200];
       int [][]hrany=new int[19900][3];
       int []priepustnost=new int[200];
       String temp="";
       String odkroj="";
       int scenar=1;      
       temp = citac.readLine();        
       pocetmiest=temp.charAt(0)-'0';
       pocetciest=temp.charAt(2)-'0';
       while(pocetmiest!=0||pocetciest!=0)
       {
           int i=0;
           int k=0;
           int j=0;
           int x,y;
           int m,n;
           int docas=0;
       
       while(i<pocetmiest)
       {
           priepustnost[i]=0;
           i++;
       }
       i=0;
       while(i<pocetciest)
       {

           temp = citac.readLine();
           for(m=0;temp.charAt(m)!=' ';m++);
           odkroj=temp.substring(0,m++);
           n=m+1;
           k=0;
           while(k<j&&!mesta[k].equals(odkroj))
           {
               k++;
           }
           if(k!=j)
           {
              x=k;
           }
           else
           {
              mesta[j]=odkroj;
              x=j;
              j++;
           }
           k=0;
           for(;temp.charAt(n)!=' ';n++);
           odkroj=temp.substring(m,n);
           while(k<j&&!mesta[k].equals(odkroj))
           {
               k++;
           }
           if(k!=j)
           {
              y=k;
           }
           else
           {
              mesta[j]=odkroj;
              y=j;
              j++;
           }
           docas=0;
           n++;
           while(n<temp.length())
           {
               docas=docas*10+temp.charAt(n)-'0';
               n++;
           }
           
           hrany[i][0]=x;
           hrany[i][1]=y;
           hrany[i][2]=docas;
           i++;
       }
       temp=citac.readLine();
       for(m=0;temp.charAt(m)!=' ';m++);
           odkroj=temp.substring(0,m++);
           n=m+1;
       k=0;
       while(k<j&&!mesta[k].equals(odkroj))
       {
               k++;
       }
       x=k;
       k=0;
       
       odkroj=temp.substring(m,temp.length());
       while(k<j&&!mesta[k].equals(odkroj))
       {
               k++;
       }
       y=k;
       priepustnost[x]=10000;
       i=0;
       while(i<pocetmiest)
       {
           k=0;
           while(k<pocetciest)
           {
               if(min(priepustnost[hrany[k][0]],hrany[k][2])>priepustnost[hrany[k][1]])
               {
                   priepustnost[hrany[k][1]]=min(priepustnost[hrany[k][0]],hrany[k][2]);
               }
               if(min(priepustnost[hrany[k][1]],hrany[k][2])>priepustnost[hrany[k][0]])
               {
                   priepustnost[hrany[k][0]]=min(priepustnost[hrany[k][1]],hrany[k][2]);
               }
               k++;
           }
           i++;
       }
       if(x!=y)
       {System.out.printf("Scenario #%d\n%d tons\n\n",scenar,priepustnost[y]);}
       else
       {
           System.out.printf("Scenario #%d\n0 tons\n\n",scenar);
       }
       scenar++;           
       temp = citac.readLine();            
       pocetmiest=temp.charAt(0)-'0';
       pocetciest=temp.charAt(2)-'0';
       }}
       catch(java.io.IOException e)
       {
               
       }
       
    }

}

Re: 544 - heavy cargo

Posted: Wed Mar 26, 2014 1:09 am
by brianfry713
You're assuming n and r are only one digit.
All times are UTC+02:00
Page 2 of 3

Powered by phpBB® Forum Software © phpBB Limited