PTA A_1072 Gas Station
传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072解：
迪杰斯特拉
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1050;
int n, m, k, ds;
int d;
bool vis;
int G;
int trans(char *s)
{
int id;
if (*s == 'G')
{
sscanf(s + 1, "%d", &id);
id += n;
}
else
sscanf(s, "%d", &id);
return id;
}
void DJS(int st)
{
fill(d, d + maxn, INT_MAX);
memset(vis, false, sizeof(vis));
d = 0;
for (int i = 1; i < n + m; i++)
{
int u= -1, min = INT_MAX;
for (int j = 1; j <= n + m; j++)
if (!vis && d < min) min = d;
if (u == -1) return;
vis = true;
for (int v = 1; v <= n + m; v++)
{
if (vis || G == INT_MAX) continue;
if (G + d < d) d = G + d;
}
}
}
int main(void)
{
// freopen("input.txt", "r", stdin);
scanf("%d %d %d %d", &n, &m, &k, &ds);
fill(G, G + maxn * maxn, INT_MAX);
while (k--)
{
char s1, s2;
int a, b, l;
scanf("%s %s %d", s1, s2, &l);
a = trans(s1);
b = trans(s2);
G = G = l;
}
int max_id = -1, max = INT_MIN;
double ave;
for (int i = n + 1; i <= n + m; i++)
{
DJS(i);
int temp = d, total = 0;
bool flag = false;
for (int j = 1; j <= n; j++)
{
if (d > ds)
{
flag = true;
break;
}
total += d;
if (d < temp) temp = d;
}
if (flag) continue;
ave = (double)total / (double)n;
if (temp > max || (temp == max && ave < ave))
{
max = temp;
max_id = i;
}
}
if (max_id == -1) puts("No Solution");
else printf("G%d\n%.1f %.1f\n", max_id - n, (double)max, ave);
return 0;
}
页:
[1]