10171 - Meeting Prof. Miguel...

[brianfry713]

Change your code to:

Code: Select all

class IntegerPair implements Comparable{
    int cost;int loc;
    public IntegerPair(int cost,int loc){
        this.cost = cost;
        this.loc = loc;
    }
    public int compareTo(Object o) {
        if(this.cost != ((IntegerPair)o).cost)
            return this.cost - ((IntegerPair)o).cost;
        return this.loc - ((IntegerPair)o).loc;
    }
   
}

[thewill]

WHY GETTIN WA FOR 10171
HERE IS MY CODE

Code: Select all

#include<iostream>
#include<cstdio>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
#include<deque>
#include<iterator>
#include<assert.h>
#include<bitset>
#include<climits>
#include<ctime>
#include<complex>
using namespace std;
int main()
{
    char a,b,c,d,x,y;
    vector<char>v3;
    int enrgy,n,i,j,k,cnt,temp;
    long int path1[30][30],path2[30][30],fpath;
    while(scanf("%d",&n)==1)
    {
        if(n==0)
        {
            break;
        }
        v3.clear();
        for(i=0;i<30;i++)
        {
            for(j=0;j<30;j++)
            {
                path1[i][j]=200000;
                path2[i][j]=200000;
            }
        }
        for(i=0;i<30;i++)
        {
            path1[i][i]=0;
            path2[i][i]=0;
        }
        map<char,int>ma;
        map<int,char>am;
        cnt=1;
        for(i=1;i<=n;i++)
        {
            cin>>a>>b>>c>>d>>enrgy;
            if(a=='Y')
            {
            if(!ma[c])
            {
                ma[c]=cnt++;
                am[cnt-1]=c;
            }
            if(!ma[d])
            {
                ma[d]=cnt++;
                am[cnt-1]=d;
            }
            if(b=='U')
            {
                path1[ma[c]][ma[d]]=enrgy;
            }
            else
            {
                path1[ma[c]][ma[d]]=enrgy;
                path1[ma[d]][ma[c]]=enrgy;
            }
            }
            else
            {
            if(!ma[c])
            {
                ma[c]=cnt++;
                am[cnt-1]=c;
            }
            if(!ma[d])
            {
                ma[d]=cnt++;
                am[cnt-1]=d;
            }
            if(b=='U')
            {
                path2[ma[c]][ma[d]]=enrgy;
            }
            else
            {
                path2[ma[c]][ma[d]]=enrgy;
                path2[ma[d]][ma[c]]=enrgy;
            }
            }

        }
        for(k=1;k<=cnt-1;k++)
        {
            for(i=1;i<=cnt-1;i++)
            {
                for(j=1;j<=cnt-1;j++)
                {
                    path1[i][j]=min(path1[i][j],path1[i][k]+path1[k][j]);
                    path2[i][j]=min(path2[i][j],path2[i][k]+path2[k][j]);
                }
            }
        }
        cin>>x>>y;
        fpath=pow(10,9);
        for(k=1;k<=cnt-1;k++)
        {
            if(fpath>path1[ma[x]][k]+path2[ma[y]][k])
            {
                fpath=path1[ma[x]][k]+path2[ma[y]][k];
                temp=k;
            }
        }
        for(k=1;k<=cnt-1;k++)
        {
            if(path1[ma[x]][k]+path2[ma[y]][k]==fpath)
            {
                v3.push_back(am[k]);
            }
        }
        sort(v3.begin(),v3.end());
        if(fpath<200000)
        {
            cout<<fpath<<" ";
            for(i=0;i<v3.size()-1;i++)
            {
                cout<<v3[i]<<" ";
            }
            cout<<v3[i]<<endl;
        }
        else
        {
            printf("You will never meet.\n");
        }
    }
    return 0;
}

[brianfry713]

It looks like you figured it out.

[nbacool2]

So I kept getting WA when my Floyd-Warshall algorithm appeared to be correct. One of the posts pointed out that there are self loops which were the problem. I memset-ed my whole matrix to infinity and the diagonal (i, i) to 0 but since there are self loops it replaced the 0 with not the optimal value. I Just skipped the cases in which city1 == city2 and got AC. Thanks people

[refatsardar]

@Brianfry sir,
Is these valid input?
I got this input from your given sample input output.
3
Y U X Y 5
M B A Y 10
Y B X Y 10
X A
2
Y U A B 10
Y U A B 100
A B
For first test case, Young_energy[X][Y] = 5 ,Young_energy[X][Y] = 10
there are different cost for direct path of X to Y.
Little bit confused to see this type of input.
I have used adjacency matrix so Young_energy[X][Y] is modified to 5 to 10 and getting result 20 Y and your result is 15 Y
Would u Please explain this matter about multiple cost for same road.

[brianfry713]

My AC code uses an adjacency list so it handles cases like that by taking the minimum.

[alecassis]

Can anybody help me? I pass every test case on this thread but keep geting WA.

Thanks in advance.

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

#define MAX 28
#define INF 1000000000

using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii; 

int memo_old[MAX][MAX];
int memo_all[MAX][MAX];


bool myfunction(const ii &a, const ii &b) {
	if (a.first > b.first)
		return true;
	if (a.first < b.first)
		return true;
	return a.second < b.second;

}

void initmemo() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (i == j) {
				memo_all[i][j] = 0;
				memo_old[i][j] = 0;
			}
			else {
				memo_all[i][j] = INF;
				memo_old[i][j] = INF;
			}
		}
	}
}


int main () {
	int t, cost;
	char classifier, direction, init, dest, init_old, init_all;
	while (scanf("%d%*c", &t) == 1) {
		if (!t) return 0;
		initmemo();
		while (t--) {
			scanf("%c %c %c %c %d%*c", &classifier, &direction, &init, &dest, &cost);
			if (classifier == 'M') {
				if (direction == 'U') {
					if (cost < memo_old[init-'A'][dest-'A'])
						memo_old[init-'A'][dest-'A'] = cost;
				}
				else {
					if (cost < memo_old[init-'A'][dest-'A'])
						memo_old[init-'A'][dest-'A'] = cost;
					if (cost < memo_old[dest-'A'][init-'A'])
						memo_old[dest-'A'][init-'A'] = cost;
				}
			}
			else {
				if (direction == 'U') {
					if (cost < memo_all[init-'A'][dest-'A'])
						memo_all[init-'A'][dest-'A'] = cost;
				}
				else {
					if (cost < memo_all[init-'A'][dest-'A'])
						memo_all[init-'A'][dest-'A'] = cost;
					if (cost < memo_all[dest-'A'][init-'A'])
						memo_all[dest-'A'][init-'A'] = cost;
				}
			}
		}
		for (int k = 0; k < MAX; k++) {
			for (int i = 0; i < MAX; i++) {
				for (int j = 0; j < MAX; j++) {
					memo_all[i][j] = min(memo_all[i][j], memo_all[i][k] + memo_all[k][j]);
					memo_old[i][j] = min(memo_old[i][j], memo_old[i][k] + memo_old[k][j]);
				}
			}
		}
		scanf("%c %c", &init_all, &init_old);
		init_all -= 'A';
		init_old -= 'A';
		vii ans;
		for (int i = 0; i < MAX; i++) {
			if (memo_old[init_old][i] != INF && memo_all[init_all][i] != INF) {
					ans.push_back(ii(memo_old[init_old][i] + memo_all[init_all][i], i));
			}
		}
		sort(ans.begin(), ans.end(), myfunction);
		int min;
		if (!ans.empty()) {
			int min = ans[0].first;
			printf("%d %c", min, ans[0].second + 'A');
			for (int i = 1; i < ans.size(); i++) {
				if (ans[i].first > min)
					break;
				else if (ans[i].first == min)
					printf(" %c", ans[i].second + 'A');
			}
			printf("\n");
		}
		else {
			printf("You will never meet.\n");
		}

	}
	return 0;
}

[brianfry713]

Try the random input at http://www.udebug.com/UVa/10171

[Najat]

I think the input file contains graph having self loops. But you have to consider the cost as 0 ignoring the loop's cost.