Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: iso8859-2
Méret: 4 KB
#include <cstdio>
#include <iostream>
#include <string>
#include <math.h>
#define INF 1000000000
using namespace std;
int num_items, num_stores, price_of_gas;
struct store
{
int id;
int x, y;
int item_count;
int* items;
};
void beolvas(char* fnin, char* fnout);
double solve();
double min(store* s, unsigned int list, bool romlando, unsigned int beento);
double distance(store* s1, store* s2, bool home);
store* stores;
bool* items_romlando;
double*** dp;
double*** dp_distance;
int main()
{
beolvas("D-large-practice.in", "D-large-practice.out");
cin.get();
return 0;
}
double solve()
{
dp = new double**[num_stores];
for (int i = 0; i < num_stores; i++)
{
dp[i] = new double*[1<<num_items];
for (int j = 0; j < (1 << num_items); j++)
{
dp[i][j] = new double[2];
dp[i][j][0] = -1;
dp[i][j][1] = -1;
}
}
dp_distance = new double**[num_stores];
for (int i = 0; i < num_stores; i++)
{
dp_distance[i] = new double*[num_stores];
for (int j = 0; j < num_stores; j++)
{
dp_distance[i][j] = new double[2];
dp_distance[i][j][0] = -1;
dp_distance[i][j][1] = -1;
}
}
return min(&stores[0], (1 << num_items) - 1 , false, 0);
}
double min(store* s, unsigned int list, bool romlando, unsigned int beento)
{
if (dp[s->id][list][romlando] != -1)
return dp[s->id][list][romlando];
double opt = INF;
double tmp = INF;
if (s->id == 0)
{
for (int i = 1; i < num_stores; i++)
{
tmp = min(&stores[i], list, false, 0) + distance(s, &stores[i], false);
if (tmp < opt)
opt = tmp;
}
} else
{
bool cont = true;
for (int i = 0; i < num_items && cont; i++)
if (list >> i & 1 && s->items[i] != -1)
for (int j = 1; j < num_stores && cont; j++)
{
store* next = &stores[j];
unsigned int nextlist = list - (1 << i);
int price = s->items[i];
if (nextlist == 0)
{
tmp = distance(s, &stores[0], false) + price;
cont = false;
} else if (s == next)
tmp = min(&stores[j], nextlist, romlando | items_romlando[i], beento) + price;
else if (!(beento >> j & 1))
tmp = min(next, nextlist, false, beento | (1 << j)) + distance(s, next, romlando | items_romlando[i]) + price;
else
continue;
if (tmp < opt)
opt = tmp;
}
}
dp[s->id][list][romlando] = opt;
return opt;
}
inline double distance(store* s1, store* s2, bool rom)
{
if (dp_distance[s1->id][s2->id][rom] != -1)
return dp_distance[s1->id][s2->id][rom];
double dist;
if (rom)
dist = distance(s1, &stores[0], false) + distance(&stores[0], s2, false);
else
dist = sqrt(pow(s1->x - s2->x, 2) + pow(s1->y - s2->y, 2)) * price_of_gas;
dp_distance[s1->id][s2->id][rom] = dist;
return dp_distance[s1->id][s2->id][rom];
}
void beolvas(char* fnin, char* fnout)
{
int n;
FILE* reader = fopen(fnin, "r");
FILE* printer = fopen(fnout, "w");
fscanf(reader, "%d", &n);
for (int caseid = 0; caseid < n; caseid++)
{
fscanf(reader, "%d %d %d", &num_items, &num_stores, &price_of_gas);
string* item_names = new string[num_items];
items_romlando = new bool[num_items];
fill(items_romlando, items_romlando + num_items, false);
for (int i = 0; i < num_items; i++)
{
char str[100];
fscanf(reader, "%s", str);
item_names[i] = str;
if (item_names[i][item_names[i].length() - 1] == '!')
{
items_romlando[i] = true;
item_names[i].erase(item_names[i].begin() + item_names[i].length() - 1);
}
}
int tmp;
char c;
stores = new store[++num_stores];
stores[0].x = stores[0].y = 0;
for (int i = 0; i < num_stores; i++)
{
stores[i].id = i;
stores[i].item_count = 0;
stores[i].items = new int[num_items];
fill(stores[i].items, stores[i].items + num_items, -1);
if (i != 0)
{
string str;
fscanf(reader, "%d %d", &stores[i].x, &stores[i].y);
fscanf(reader, "%c", &c);
while (c != '\n' && !feof(reader))
{
if (c != ' ')
{
if (c != ':')
str += c;
else
{
int id = -1;
for (int j = 0; j < num_items; j++)
if (str.compare(item_names[j]) == 0)
id = j;
fscanf(reader, "%d", &tmp);
stores[i].items[id] = tmp;
stores[i].item_count++;
}
} else
str = "";
fscanf(reader, "%c", &c);
}
}
}
double result = solve();
printf("Case #%d: %.7f \n", caseid + 1, result);
fprintf(printer, "Case #%d: %.7f \n", caseid + 1, result);
}
fclose(reader);
fclose(printer);
}
