【HDOJ】1601 Galactic Import

Dijkstra。

 /* 1601 */
#include <cstdio>
#include <cstring>
#include <cstdlib> #define INF 999999 char buf[];
int map[][];
bool visit[], valid[];
double val[];
int path[];
int n; void dijkstra() {
int i, j, k;
int min, v; memset(visit, false, sizeof(visit));
visit[] = true;
for (i=; i<; ++i)
path[i] = map[i][]; for (i=; i<; ++i) {
min = INF;
for (j=; j<; ++j) {
if (!visit[j] && path[j]<min) {
min = path[j];
v = j;
}
}
if (min == INF)
break;
visit[v] = true;
for (j=; j<; ++j) {
if (!visit[j] && path[j]>min+map[v][j]) {
path[j] = min + map[v][j];
}
}
}
} int main() {
int i, j, k, r;
double v, max;
char cmd[], line[]; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%d",&n)!=EOF) {
for (i=; i<; ++i) {
for (j=; j<; ++j) {
map[i][j] = INF;
}
map[i][i] = ;
}
for (i=; i<n; ++i) {
scanf("%s %lf %s", cmd, &v, line);
j = cmd[] - 'A';
val[j] = v;
for (r=; line[r]; ++r) {
if (line[r] == '*')
k = ;
else
k = line[r] - 'A';
map[j][k] = map[k][j] = ;
}
}
dijkstra();
max = -;
v = ;
for (i=; i<; ++i) {
if (path[i] >= INF)
continue;
if (path[i] > ) {
j = path[i]-;
while (j--) {
val[i] *= 0.95;
}
}
if (val[i] > max) {
max = val[i];
v = i;
}
}
printf("Import from %c\n", (char)v+'A');
} return ;
}
上一篇:TCP 的那些事儿(下)(转)


下一篇:TCP的那些事儿(上)