## 10171 - Meeting Prof. Miguel...

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

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;
}

}``````
Check input and AC output for thousands of problems on uDebug!

thewill
New poster
Posts: 6
Joined: Wed Dec 04, 2013 10:18 am

### Re: 10171 - Meeting Prof. Miguel

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,path2,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;
}``````
Last edited by brianfry713 on Sat Jan 17, 2015 1:00 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 10171 - Meeting Prof. Miguel

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
New poster
Posts: 6
Joined: Sat Jun 07, 2014 10:22 pm

### Re: 10171 - Meeting Prof. Miguel...

@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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel...

My AC code uses an adjacency list so it handles cases like that by taking the minimum.
Check input and AC output for thousands of problems on uDebug!

alecassis
New poster
Posts: 10
Joined: Sat Sep 20, 2014 6:36 am

### Re: 10171 - Meeting Prof. Miguel...

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

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.first;
printf("%d %c", min, ans.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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10171 - Meeting Prof. Miguel...

Try the random input at http://www.udebug.com/UVa/10171
Check input and AC output for thousands of problems on uDebug!

Najat
New poster
Posts: 1
Joined: Tue May 03, 2016 5:36 pm

### Re: 10171 - Meeting Prof. Miguel...

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