INPUT
Code: Select all
2
Y U A B 10
Y U A B 100
A B
0
Code: Select all
10 B
Code: Select all
100 B
Moderator: Board moderators
Code: Select all
2
Y U A B 10
Y U A B 100
A B
0
Code: Select all
10 B
Code: Select all
100 B
Code: Select all
#include<stdio.h> // WA
#define INF -32768
#define MAX 27
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
long distance_pm[MAX][MAX], distance_sm[MAX][MAX], alpha_pm[MAX], alpha_sm[MAX];
void initial()
{
long i, j;
for(i = 0; i < MAX; i++)
alpha_pm[i] = alpha_sm[i] = 0;
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
{
if(i != j)
{
distance_sm[i][j] = INF;
distance_pm[i][j] = INF;
}
else
{
distance_sm[i][j] = 0;
distance_pm[i][j] = 0;
}
}
}
void Floyd_Warshall()
{
long i, j, k;
for(k = 0; k < MAX; k++)
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
{
if(alpha_sm[i] && alpha_sm[j] && alpha_sm[k])
distance_sm[i][j] = max(distance_sm[i][j], min(distance_sm[i][k], distance_sm[k][j]));
if(alpha_pm[i] && alpha_pm[j] && alpha_pm[k])
distance_pm[i][j] = max(distance_pm[i][j], min(distance_pm[i][k], distance_pm[k][j]));
}
}
void main()
{
long edge, w, i, temp, min;
char type, dir, u, v, sahriar, miguel, mitting[MAX], m;
//freopen("E:\\test.txt", "rt", stdin);
while(scanf("%ld", &edge) == 1 && edge)
{
initial();
for(i = 0; i < edge; i++)
{
scanf(" %c %c %c %c %ld", &type, &dir, &u, &v, &w);
if(type == 'Y')
{
alpha_sm[u-'A'] = alpha_sm[v-'A'] = 1;
if(dir == 'U')
{
if(distance_sm[u-'A'][v-'A'] == INF || distance_sm[u-'A'][v-'A'] < -w)
distance_sm[u-'A'][v-'A'] = -w;
}
else
{
if(distance_sm[u-'A'][v-'A'] == INF || distance_sm[u-'A'][v-'A'] < -w)
{
distance_sm[u-'A'][v-'A'] = -w;
distance_sm[v-'A'][u-'A'] = -w;
}
}
}
else
{
alpha_pm[u-'A'] = alpha_pm[v-'A'] = 1;
if(distance_pm[u-'A'][v-'A'] == INF || distance_pm[u-'A'][v-'A'] < -w)
{
if(dir == 'U')
distance_pm[u-'A'][v-'A'] = -w;
else
{
distance_pm[u-'A'][v-'A'] = -w;
distance_pm[v-'A'][u-'A'] = -w;
}
}
}
}
Floyd_Warshall();
scanf(" %c %c", &sahriar, &miguel);
min = INF;
for(i = 0; i < MAX; i++)
{
if(distance_sm[sahriar - 'A'][i] != INF && distance_pm[miguel - 'A'][i] != INF)
{
temp = distance_sm[sahriar - 'A'][i] + distance_pm[miguel - 'A'][i];
if(temp > min)
{
m = 0;
min = temp;
mitting[m++] = i + 'A';
}
else if(temp == min)
{
mitting[m++] = i + 'A';
}
}
}
if(min != INF)
{
printf("%ld", (-1)*min);
for(i = 0; i < m; i++)
printf(" %c", mitting[i]);
printf("\n");
}
else
printf("You will never meet.\n");
}
}
Code: Select all
#include <stdio.h>
#define MAX 162500
#define N 26
int manzoor[N][N], profmiguel[N][N] ;
void main() {
int m, c, min, i, j, k ;
char p, q, u, v, a, b ;
while ( scanf ( "%d", &m ), m ) {
for ( i=0; i<N; i++ )
for ( j=0; j<N; j++ )
manzoor[i][j] = profmiguel[i][j] = i == j ? 0 : MAX ;
for ( i=0; i<m; i++ ) {
scanf ( " %c %c %c %c %d", &p, &q, &u, &v, &c ) ;
if ( p == 'Y' )
if ( q == 'U' )
manzoor[u-'A'][v-'A'] = c ;
else
manzoor[u-'A'][v-'A'] = manzoor[v-'A'][u-'A'] = c ;
else
if ( q == 'U' )
profmiguel[u-'A'][v-'A'] = c ;
else
profmiguel[u-'A'][v-'A'] = profmiguel[v-'A'][u-'A'] = c ;
}
for ( k=0; k<N; k++ )
for ( i=0; i<N; i++ )
for ( j=0; j<N; j++ ) {
if ( manzoor[i][k] + manzoor[k][j] < manzoor[i][j] )
manzoor[i][j] = manzoor[i][k] + manzoor[k][j] ;
if ( profmiguel[i][k] + profmiguel[k][j] < profmiguel[i][j] )
profmiguel[i][j] = profmiguel[i][k] + profmiguel[k][j] ;
}
scanf ( " %c %c", &a, &b ) ;
min = MAX ;
for ( i=0; i<N; i++ )
if ( manzoor[a-'A'][i] + profmiguel[b-'A'][i] < min )
min = manzoor[a-'A'][i] + profmiguel[b-'A'][i] ;
if ( min == MAX )
printf ( "You will never meet.\n" ) ;
else {
printf ( "%d", min ) ;
for ( i=0; i<N; i++ )
if ( manzoor[a-'A'][i] + profmiguel[b-'A'][i] == min )
printf ( " %c", i+'A' );
putchar ( '\n' ) ;
}
}
}
Code: Select all
#include<stdio.h>
#include<string.h>
char source,source1,destination;
char destination1,direction,age;
int old[28][28],young[28][28],array[28],array1[28];
int old_path[28][28],young_path[28][28],data[28];
main()
{
int n,i,j,k,p,a,b,c;
int flag,val;
int dis,dis1,cost,temp;
freopen("10171a.in","rt",stdin);
while(scanf("%d\n",&n)==1)
{
if(n==0)
break;
memset(array,0,sizeof(array));
for(i=0;i<28;i++)
{
for(j=0;j<28;j++)
{
old[i][j]=10000000;
young[i][j]=10000000;
old_path[i][j]=0;
young_path[i][j]=0;
}
old[i][i]=0;
young[i][i]=0;
old_path[i][i]=1;
young_path[i][i]=1;
}
flag=0;j=0;c=0;
for(p=0;p<n;p++)
{
scanf("%c %c %c %c %d\n",&age,&direction,&source,&destination,&val);
a=source-65;
b=destination-65;
if(c<b)
c=b;
else if(c<a)
c=a;
if(age=='Y')
{
if(direction=='U')
{
young[a][b]=val;
young_path[a][b]=1;
}
else
{
young[a][b]=val;
young[b][a]=val;
young_path[a][b]=1;
young_path[b][a]=1;
}
}
else if(age=='M')
{
if(direction=='U')
{
old[a][b]=val;
old_path[a][b]=1;
}
else
{
old[a][b]=val;
old[b][a]=val;
old_path[a][b]=1;
old_path[b][a]=1;
}
}
}
scanf("%c %c\n",&source1,&destination1);
a=source1-65;
b=destination1-65;
if(c<a)
c=a;
else if(c<b)
c=b;
for(k=0;k<=c;k++)
{
for(i=0;i<=c;i++)
{
for(j=0;j<=c;j++)
{
dis=old[i][k]+old[k][j];
if(old[i][j]>dis)
old[i][j]=dis;
old_path[i][j]=old_path[i][j]|(old_path[i][k]&old_path[k][j]);
dis1=young[i][k]+young[k][j];
if(young[i][j]>dis1)
young[i][j]=dis1;
young_path[i][j]=young_path[i][j]|(young_path[i][k]&young_path[k][j]);
}
}
}
for(i=0;i<=c;i++)
array1[i]=i;
for(i=0;i<=c;i++)
{
if(young_path[a][i]==0||old_path[b][i]==0)
array[i]=-1;
else
array[i]=young[a][i]+old[b][i];
}
for(i=0;i<=c;i++)
for(j=i+1;j<=c;j++)
{
if(array[j]<array[i])
{
temp=array[j];
array[j]=array[i];
array[i]=temp;
temp=array1[j];
array1[j]=array1[i];
array1[i]=temp;
}
}
flag=0;j=0;
for(i=0;i<=c;i++)
{
if(array[i]!=-1&&flag==0)
{
cost=array[i];
data[j]=array1[i];
j++;
flag=1;
}
else if(cost==array[i])
{
data[j]=array1[i];
j++;
}
else
continue;
}
if(flag==0)
printf("You will never meet.\n");
else
{
printf("%d ",cost);
for(i=0;i<j;i++)
{
if(i==j-1)
printf("%c\n",data[i]+65);
else
printf("%c ",data[i]+65);
}
}
}
}
Code: Select all
input:
4
Y U A B 4
Y U C A 1
M U D B 6
M B C D 2
A D
2
Y U A B 10
M U C D 20
A D
6
Y U A Z 0
Y U C A 0
Y U A Y 0
M U D Z 0
M B C D 0
M B C Y 0
A D
2
Y U B D 0
M U B D 0
B B
2
Y U A B 0
M U A B 0
A C
2
Y U A B 0
M U A B 0
C C
2
Y U A Z 10
Y U A B 20
K K
2
Y U X Z 1
Y U X Z 10
X Z
2
M U X Z 1
M U X Z 10
X Z
2
M U X Z 1
Y U X Z 10
X Z
2
Y U A B 0
M U B A 10
A B
3
Y U A B 5
M B B C 5
M U B A 10
A B
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
0
output:
10 B
You will never meet.
0 Y Z
0 B D
You will never meet.
0 C
0 K
1 Z
You will never meet.
10 Z
0 B
5 B
15 Y
10 B
Press any key to continue
Code: Select all
#include <stdio.h>
const int MAX=30;
const int INF = 1000000;
int d_m[MAX+1];
int c_m[MAX+1][MAX+1];
int d_p[MAX+1];
int c_p[MAX+1][MAX+1];
bool flag[MAX+1];
void Dijkstra_m(int beg, int n)
{
int i, j, u, tmp;
for(i = 0; i <= n; i++)
{
d_m[i] = c_m[beg][i];
flag[i] = false;
}
d_m[beg] = 0; flag[beg] = true;
for(i = 1; i <= n; i++)
{
tmp = INF; u = beg;
for(j = 1; j <=n; j++)
{
if(!flag[j] && d_m[j] < tmp)
{
u = j;
tmp = d_m[j];
}
}
flag[u] = true;
for(j = 1; j <= n; j++)
{
if(!flag[j] && c_m[u][j] < INF)
{
if(d_m[u] + c_m[u][j] < d_m[j])
d_m[j] = d_m[u] + c_m[u][j];
}
}
}
}
void Dijkstra_p(int beg, int n)
{
int i, j, u, tmp;
for(i = 0; i <= n; i++)
{
d_p[i] = c_p[beg][i];
flag[i] = false;
}
d_p[beg] = 0; flag[beg] = true;
for(i = 1; i <= n; i++)
{
tmp = INF; u = beg;
for(j = 1; j <=n; j++)
{
if(!flag[j] && d_p[j] < tmp)
{
u = j;
tmp = d_p[j];
}
}
flag[u] = true;
for(j = 1; j <= n; j++)
{
if(!flag[j] && c_p[u][j] < INF)
{
if(d_p[u] + c_p[u][j] < d_p[j])
d_p[j] = d_p[u] + c_p[u][j];
}
}
}
}
int main()
{
int NoOfCon;
char line[100];
char buffer;
char young, dir,start,sourse;
int energy;
char prof,me;
while(1)
{
NoOfCon = 0;
for(int i=0;i<=MAX;i++)
for(int j=0;j<=MAX;j++)
{
c_m[i][j]=INF;
c_p[i][j]=INF;
}
gets(line);
sscanf(line,"%d",&NoOfCon);
if(NoOfCon==0)
break;
for(int i=0;i<NoOfCon;i++)
{
gets(line);
sscanf(line,"%c%c%c%c%c%c%c%d",&young,&buffer,&dir,&buffer,&start,&buffer,&sourse,&energy);
if(young=='Y')
{
if(c_m[start-'A'+1][sourse-'A'+1]> energy)
c_m[start-'A'+1][sourse-'A'+1] = energy;
if(dir =='B')
if(c_m[sourse-'A'+1][start-'A'+1] > energy)
c_m[sourse-'A'+1][start-'A'+1]=energy;
}
else
{
if(c_p[start-'A'+1][sourse-'A'+1] > energy)
c_p[start-'A'+1][sourse-'A'+1]=energy;
if(dir =='B')
if(c_p[sourse-'A'+1][start-'A'+1]> energy)
c_p[sourse-'A'+1][start-'A'+1]=energy;
}
}
gets(line);
sscanf(line,"%c%c%c",&me,&buffer,&prof);
Dijkstra_m(me-'A'+1,MAX);
Dijkstra_p(prof-'A'+1,MAX);
int min=INF;
char loca;
bool first= true;
int count = 0;
char meet[MAX];
for(int i=1;i<=MAX;i++)
{
if(d_m[i]<INF&&d_p[i]<INF && (min==INF || min>d_m[i]+d_p[i]))
{
count = 0;
min = d_m[i]+d_p[i];
meet[count] = i;
}
else if(min!= INF && min == c_m[me-'A'+1][i] + c_p[prof-'A'+1][i] )
meet[++count] = i;
}
if(min!=INF)
{
printf("%d",min);
for(int i =0;i <=count;i++)
{
printf(" %c",meet[i]+'A'-1);
}
puts("");
}
else if(prof==me)
printf("0 %c\n",prof);
else
printf("You will never meet.\n");
}
return 0;
}
Code: Select all
4
Y U A B 4
Y U C A 1
M U D B 6
M B C D 2
A D
2
Y U A B 10
M U C D 20
A D
6
Y U A Z 0
Y U C A 0
Y U A Y 0
M U D Z 0
M B C D 0
M B C Y 0
A D
2
Y U B D 0
M U B D 0
B B
2
Y U A B 0
M U A B 0
A C
2
Y U A B 0
M U A B 0
C C
2
Y U A Z 10
Y U A B 20
K K
2
Y U X Z 1
Y U X Z 10
X Z
2
M U X Z 1
M U X Z 10
X Z
2
M U X Z 1
Y U X Z 10
X Z
2
Y U A B 0
M U B A 10
A B
3
Y U A B 5
M B B C 5
M U B A 10
A B
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
0
Code: Select all
10 B
You will never meet.
0 Y Z
0 B D
You will never meet.
0 C
0 K
1 Z
You will never meet.
10 Z
0 B
5 B
15 Y
10 B
Code: Select all
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
#define MAXL 35
#define MAXS 1000010
#define MAXP 90000
#define INFIN 100000000
using namespace std;
#define PQ priority_queue
#define btc(x) __builtin_popcount(x)
#define MP(x, y) make_pair(x, y)
#define PAIR pair< int, int >
#define mem(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define pi (2*acos(0))
#define oo 1<<20
#define dd double
#define ll long long int
#define llu long long unsigned
#define ERR 1e-5
#define fst first
#define sec second
#define SZ(a) (int)a.size()
#define All(a) a.begin(),a.end()
#define FOR(i,p,k) for (i=p; i<k;i++)
#define REP(i,n) for (i=0;i<n;i++)
#define REV(i,n) for (i=n;i>=0;i--)
void dfs_y(int u);
void dfs_m(int u);
int dist1[MAXL][MAXL], n;
int dist2[MAXL][MAXL];
int color1[MAXL], color2[MAXL];
vector<int>edge_y[MAXL];
vector<int>edge_m[MAXL];
vector<char>ans;
int main()
{
int i, j, k, res, indx, a, b, MIN, cst;
char st, ed;
char str[MAXL];
while(scanf(" %d", &n)==1)
{
if( n==0 ) break;
map<char , int>Input;
map<int , char>Output;
ans.clear();
mem(str,0);
for(i=0; i<MAXL; i++) edge_m[i].clear();
for(i=0; i<MAXL; i++) edge_y[i].clear();
indx = 1;
for(i=0; i<MAXL; i++){
for(j=0; j<MAXL; j++) {
dist1[i][j] = INFIN;
dist2[i][j] = INFIN;
}
dist1[i][i] = 0;
dist2[i][i] = 0;
}
for(i=1; i<=n; i++)
{
scanf(" %[^\n]", str);
if(!Input[str[4]]) {
Input[str[4]] = indx;
Output[indx] = str[4];
indx++;
}
if(!Input[str[6]]) {
Input[str[6]] = indx;
Output[indx] = str[6];
indx++;
}
if(str[0]=='Y')
{
if(str[2]=='U') {
if(Input[str[4]]==Input[str[6]]) cst = 0;
else cst = str[8]-'0';
dist1[Input[str[4]]][Input[str[6]]] = cst;
edge_y[Input[str[4]]].pb(Input[str[6]]);
}
else if(str[2]=='B') {
if(Input[str[4]]==Input[str[6]]) cst = 0;
else cst = str[8]-'0';
dist1[Input[str[4]]][Input[str[6]]] = cst;
dist1[Input[str[6]]][Input[str[4]]] = cst;
edge_y[Input[str[4]]].pb(Input[str[6]]);
edge_y[Input[str[6]]].pb(Input[str[4]]);
}
}
else if(str[0]=='M')
{
if(str[2]=='U') {
if(Input[str[4]]==Input[str[6]]) cst = 0;
else cst = str[8]-'0';
dist2[Input[str[4]]][Input[str[6]]] = cst;
edge_m[Input[str[4]]].pb(Input[str[6]]);
}
else if(str[2]=='B') {
if(Input[str[4]]==Input[str[6]]) cst = 0;
else cst = str[8]-'0';
dist2[Input[str[4]]][Input[str[6]]] = cst;
dist2[Input[str[6]]][Input[str[4]]] = cst;
edge_m[Input[str[4]]].pb(Input[str[6]]);
edge_m[Input[str[6]]].pb(Input[str[4]]);
}
}
}
for(k=1; k<indx; k++)
for(i=1; i<indx; i++)
for(j=1; j<indx; j++)
dist1[i][j] = min(dist1[i][j], (dist1[i][k] + dist1[k][j]));
for(k=1; k<indx; k++)
for(i=1; i<indx; i++)
for(j=1; j<indx; j++)
dist2[i][j] = min(dist2[i][j], (dist2[i][k] + dist2[k][j]));
cin >> st >> ed;
a = Input[st];
b = Input[ed];
mem(color1,0);
dfs_y(a);
mem(color2,0);
dfs_m(b);
MIN = INFIN;
for(i=1; i<indx; i++)
{
if(color1[i] && color2[i]) {
MIN = min(MIN , (dist1[a][i]+dist2[b][i]));
ans.pb(Output[i]);
}
}
sort(ans.begin() , ans.end());
if(SZ(ans)>0)
{
cout<<MIN;
for(i=0; i<SZ(ans); i++)
cout<<" "<<ans[i];
cout<<"\n";
}
else
cout<<"You will never meet.\n";
}
return 0;
}
void dfs_y(int u)
{
int i, j, v;
color1[u] = 1;
for(i=0; i<SZ(edge_y[u]); i++)
{
v = edge_y[u][i];
if(!color1[v])
dfs_y(v);
}
}
void dfs_m(int u)
{
int i, j, v;
color2[u] = 1;
for(i=0; i<SZ(edge_m[u]); i++)
{
v = edge_m[u][i];
if(!color2[v])
dfs_m(v);
}
}