Page 5 of 5

### Re: 10171 - Meeting Prof. Miguel

Posted: Sat Feb 15, 2014 12:08 am

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

}``````

### Re: 10171 - Meeting Prof. Miguel

Posted: Sat May 24, 2014 12:00 pm
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;
}``````

### Re: 10171 - Meeting Prof. Miguel

Posted: Wed Jun 11, 2014 11:08 pm
It looks like you figured it out.

### Re: 10171 - Meeting Prof. Miguel

Posted: Wed Aug 20, 2014 2:50 pm
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 ### Re: 10171 - Meeting Prof. Miguel...

Posted: Fri Jan 16, 2015 2:26 pm
@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

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

Posted: Sat Jan 17, 2015 1:05 am
My AC code uses an adjacency list so it handles cases like that by taking the minimum.

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

Posted: Fri Feb 13, 2015 7:34 pm
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;
}
``````

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

Posted: Fri Feb 13, 2015 11:56 pm
Try the random input at http://www.udebug.com/UVa/10171

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

Posted: Wed Jun 28, 2017 2:37 pm
I think the input file contains graph having self loops. But you have to consider the cost as 0 ignoring the loop's cost.