1000 – Airport Configuration
Discussion:
Adhoc. Just Calculate cost for each configuration in O(n*n). Then sort and print the result. Beware of printing. There is only a space between “Configuration” and “Load”.
Click to See Code
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define Ulong unsigned long long
#define FOR(I,A,B) for(int I = (A); I < (B) ; ++ I)
#define REP(i,n) for( int i=0 ; i < n ; i++ )
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
#define EPS 1e-9
#define F first
#define S second
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(x) int x;scanf("%d",&x)
#define Si(x) scanf("%d",&x);
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
#define IO ios_base::sync_with_stdio(0);cin.tie(0)
#define READ freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)
inline long long bigmod(long long p,long long e,long long M){
long long ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/***************************** END OF TEMPLATE *******************************/
const int N = 1001;
int A[30][30];
int a[30],b[30];
bool cmp(pair<int,int> a, pair<int,int> b)
{
if(a.S==b.S)return a.F<b.F;
return a.S<b.S;
}
int main()
{
int n,p,v,d,k,con;
while(scanf("%d",&n)==1 &&n) {
memset(A,0,sizeof A);
for(int i=1;i<=n;i++){
scanf("%d %d",&p,&k);
for(int j=0;j<k;j++){
scanf("%d %d",&d,&v);
A[p][d] = v;
}
}
vector<pair<int,int> > v;
while(scanf("%d",&con)==1 && con) {
for(int i=1;i<=n;i++) { scanf("%d",&p);a[p] = i;}
for(int i=1;i<=n;i++) { scanf("%d",&p);b[p] = i;}
int ans = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) {
int x = abs(a[i]-b[j]),y=1;
ans += (x+1)*A[i][j];
}
}
v.push_back(mp(con,ans));
}
sort(all(v),cmp);
printf("Configuration Load\n");
for(int i=0;i < v.size();i++) {
printf("%5d %d\n",v[i].F, v[i].S);
}
}
}
/*
3
1 2 2 10 3 15
2 1 3 10
3 2 1 12 2 20
100
1 2 3
2 3 1
2
2 3 1
3 2 1
0
2
1 1 2 100
2 1 1 200
1
1 2
1 2
2
1 2
2 1
0
0
*/
1001 – Say Cheese
Discussion:
Think two terminal points as sphere of radius 0. Then we have some sphere, Our goal is to reach a sphere to another with minimal cost. Sounds like Dijkastra Algorithm.
What are the edges?
We can go each sphere to other. So we have edges connecting each to others. And the cost? You can figure it out.
Click to See Code
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define Ulong unsigned long long
#define FOR(I,A,B) for(int I = (A); I < (B) ; ++ I)
#define REP(i,n) for( int i=0 ; i < n ; i++ )
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
#define EPS 1e-9
#define F first
#define S second
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(x) int x;scanf("%d",&x)
#define Si(x) scanf("%d",&x);
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
#define IO ios_base::sync_with_stdio(0);cin.tie(0)
#define READ freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)
inline long long bigmod(long long p,long long e,long long M){
long long ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/***************************** END OF TEMPLATE *******************************/
const int N = 105;
int x[N],y[N],z[N],r[N];
double dist[N];
double calc(int i,int j) // cost to go from i to j
{
return max(0.0, sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]) + (z[i]-z[j]) * (z[i]-z[j])) - r[i] - r[j]);
}
double dij(int s,int d,int n)
{
set<pair<double,int> > pq;
pq.insert(mp(0,s));
for(int i=0;i<N;i++) dist[i]=1e9;
dist[s] = 0;
while(pq.size()){
auto u = *pq.begin(); pq.erase(u);
if(u.S==d) {
return u.F;
}
for(int i = 0;i < n; i ++) {
if(dist[i] > dist[u.S] + calc(u.S,i)) {
dist[i] = dist[u.S] + calc(u.S,i);
pq.insert(mp(dist[i],i));
}
}
}
return 0;
}
int main()
{
int n,cs=0;
while(scanf("%d",&n)==1) {
if(n==-1)break;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x[i],&y[i],&z[i],&r[i]);
}
scanf("%d %d %d",&x[n],&y[n],&z[n]);
scanf("%d %d %d",&x[n+1],&y[n+1],&z[n+1]);
r[n]= r[n+1]=0;
printf("Cheese %d: Travel time = %d sec\n",++cs,(int)(dij(n,n+1,n+2)* 10 + .5) );
}
}
/*
1
20 20 20 1
0 0 0
0 0 10
1
5 0 0 4
0 0 0
10 0 0
-1
*/
Code for Fun 