10048 - Audiophobia

[I LIKE GN]

hello all...
i can't find out my bug.....
please help meeeeeee!!!!!!!!!

Code: Select all

got acc removed...

thanks...

[I LIKE GN]

never mind
i just got the problem ACC with minor change
thank uuuuuu...

[event]

I generate the output like in example:

Code: Select all

Case #1
80
60
60
 
Case #2
40
no path
80

Does somebody knows why PE?

[chunyi81]

There should be no blank line after the last test case.

[n_arun89]

here is my code can anyone find the problem.....???????

Code: Select all

#include<iostream>
using namespace std;
long long cost[1000][1000];
int q[1000][2];
int n,e,que;

void floyd(int con){             //floyd algo
     int i,j,k;
     for(k=1;k<=n;k++){
     for(j=1;j<=n;j++){
     for(i=1;i<=n;i++){
                      
           cost[i][j]=min(cost[i][j],max(cost[i][k],cost[k][j]));
                        }
                        }
                        }
                       
                        cout<<"Case #"<<con<<endl;
                        for(i=1;i<=que;i++){
                             if(cost[q[i][0]][q[i][1]]>200000000){cout<<"no path"<<endl;}
                             else{            
                        cout<<cost[q[i][0]][q[i][1]]<<endl;}
                        }
                        
                        
                        }        


int main(){
    int x,y,i,j,intensity,con=1;
    while(cin>>n>>e>>que){
                     if(e==0 && n==0 && que==0){break;}
                     else{     
                           for(j=1;j<=n;j++){
                            for(i=1;i<=n;i++){
                                             cost[j][i]=2000000089;
                                             }            //initialising to a max
                                             }
                        
                        for(i=1;i<=e;i++){
                           cin>>x>>y>>intensity;
                           cost[x][y]=intensity;
                           cost[y][x]=intensity;
                           }                      //getting inputs
                          
                        for(i=1;i<=que;i++){
                                cin>>q[i][0]>>q[i][1];
                                }                           //getting query co-ordinates


                                floyd(con++);           //con is the test case number
                                cout<<endl;
                                }
                                } 
                                return 0;
                                }                      

[turcse143]

thanks i got acc
here just little tricks
that u have to check the new line.

[turcse143]

don't create new thread . Check the board first.

[SyFy]

Solved this problem with DSU + Kruskal + Floyed... is it ok?
Accepted JAVA 0.640

pls tell me how to solve this problem using only Floyed algo.

Thx.

[abbir.ku]

I have tried all the test cases but still wrong answer . plz help . Here is my code . I have used prims algorithm .

Code: Select all

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define pb(x) push_back(x)
#define MAX 210
#define initialize(a,b,c) for(int i=0;i<c;i++)a[i] = b
#define mem(x,y) memset(x,y,sizeof(x))
#define MAXINT 999999999
#define READ(in) freopen(in,"r",stdin)
#define WRITE(out) freopen(out,"w",stdout)

using namespace std;

struct edge{
    int vertex;
    int weight;

    bool operator < (const edge& p) const{
        return weight>p.weight;
    }
};

vector<edge> adjList[MAX];//
vector<int> trail;//
bool intree[MAX];
int parent[MAX];
int child[MAX];
int dist[MAX];
int last;

void addToList(int st,int en,int weight){
    edge e1;
    e1.vertex = en;
    e1.weight = weight;
    adjList[st].pb(e1);

    e1.vertex = st;
    e1.weight = weight;
    adjList[en].pb(e1);
}

void mst_prims(int start){
    initialize(dist,MAXINT,MAX);
    mem(parent,-1);
    mem(child,-1);
    mem(intree,false);


    edge e1,u;
    int v,w,Size;
    priority_queue<edge> pq;

    dist[start] = 0;
    intree[start] = true;
    e1.vertex = start;
    e1.weight = 0;
    pq.push(e1);

    while(!pq.empty()){
        u = pq.top();
        pq.pop();
        Size = adjList[u.vertex].size();

        intree[u.vertex] = true;

        last =u.vertex;

        rep(i,Size){
            v = adjList[u.vertex][i].vertex;
            w = adjList[u.vertex][i].weight;

            if((intree[v]==false)&&(dist[v]>w)){
                e1.vertex = v;
                e1.weight = w;
                pq.push(e1);

                parent[v] = u.vertex;
                child[u.vertex] = v;
                dist[v] = w;
            }
        }
    }
}

int parentMaximum(int last,int en){
    vector<int> weights;
    int x = last;
    while(x!=-1){
        weights.pb(dist[x]);
        x = parent[x];
    }
    sort(weights.begin(),weights.end());
    return weights[weights.size()-1];
}

int childMaximum(int en){
    vector<int> weights;
    int x = en;
    while(x!=-1){
        weights.pb(dist[x]);
        x = parent[x];

    }
    sort(weights.begin(),weights.end());
    return weights[weights.size()-1];
}


int main()
{
    //READ("in2.txt");
    //WRITE("out.txt");
    int n,e,q;
    int a,b,w;
    int st,en;
    int tCase = 0;
    int x1,x2;
    bool isThere = false;

    while(cin>>n>>e>>q){

        if( (n==0) && (e==0) && (q==0) ){
            break;
        }

        rep(i,e){
            scanf("%d %d %d",&a,&b,&w);
            addToList(a,b,w);
        }

        if(isThere){
            printf("\n");
        }
        isThere = true;

        printf("Case #%d\n",(tCase+1));
        tCase = tCase + 1;

        rep(j,q){
            scanf("%d %d",&st,&en);
            mst_prims(st);

            if( (st<=0)||(st>n)|| (en<=0)||(en>n) ){
                printf("0\n");
                continue;
            }

            if(intree[en]){
                x1 = parentMaximum(last,en);
                x2 = childMaximum(en);
                (x1<x2)?printf("%d\n",x1):printf("%d\n",x2);
            }else{
                printf("no path\n");
            }
        }

        rep(m,n+1){
            adjList[m].clear();
        }
    }

    return 0;
}

[lbv]

I have tried all the test cases but still wrong answer . plz help . Here is my code . I have used prims algorithm .

Have you really tried all test cases given here in the forums? The post just above yours, for example, contains multiple instances of cases where your code prints different answers.

Here's a few additional small cases for you to check:

Input

Code: Select all

4 6 1
1 4 32
1 2 88
2 4 70
3 2 75
3 1 81
3 4 79
2 3

5 7 1
5 3 73
4 5 91
2 5 54
1 2 26
2 4 25
4 3 6
1 4 64
1 5

5 6 1
3 2 76
4 3 23
5 1 44
2 5 70
4 1 54
3 5 85
4 2

0 0 0

Output

Code: Select all

Case #1
75

Case #2
54

Case #3
70

In addition to this, consider that running Prim's algorithm for each query has a prohibitive complexity, given the constraints described in the problem statement. There is another algorithm which can help you answer all queries much more quickly. Take your time to read the previous posts for more tips.

P.S. When posting code in the forums, please use the code tags (see the buttons above the text box while you're writing your messahge). Thanks.

[stronk111]

I can't find bug in my code. My solution is based on MST and DFS.I have tried many random test cases but still I get WA. Can you help me?

Code: Select all

removed got AC

[lighted]

Always print newline after each line, also after last line. Print blank line between test cases. I sent you PM.

[stronk111]

Thank you. I was a little confused how output should look like.