# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
26579 | wwiiiii | 주유소 (KOI16_gas) | C++14 | 1008 ms | 51900 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class edge {
public:
long long v, c;//vertex, cost
bool operator<(const edge & next) const {
if (c != next.c) return c > next.c;
else return v > next.v;
}
};
const long long vmax = 2520, emax = 4020, inf = vmax * emax * vmax;
long long n, m;
long long oil[vmax];
vector<edge> graph[vmax];
long long road[vmax][vmax];
void dijk(long long start)
{
vector<long long> d(n + 1, inf);
priority_queue<edge> pq;
pq.push({ start, 0 });
while (!pq.empty())
{
edge now = pq.top(); pq.pop();
if (now.c > d[now.v]) continue;
d[now.v] = now.c;
for (auto next : graph[now.v])
{
if (d[next.v] > d[now.v] + next.c)
{
d[next.v] = d[now.v] + next.c;
pq.push({ next.v, d[next.v] });
}
}
}
for (long long i = 1; i <= n; i++) {
if (d[i] != inf) road[start][i] = d[i] * oil[start];
}
}
long long ans()
{
vector<long long> d(n + 1, inf);
vector<bool> check(n + 1, false);
d[1] = 0;
while (true)
{
int mini = 0;
for (int i = 1; i <= n; i++)
{
if (check[i]) continue;
if (d[mini] > d[i]) mini = i;
}
if (mini == 0) break;
for (int next = 1; next <= n; next++)
{
if (d[next] > d[mini] + road[mini][next])
{
d[next] = d[mini] + road[mini][next];
}
}
check[mini] = true;
}
return d[n];
}
int main()
{
scanf("%lld %lld", &n, &m);
for (long long i = 1; i <= n; i++) scanf("%lld", &oil[i]);
for (long long i = 0; i < m; i++)
{
long long s, e, c; scanf("%lld %lld %lld", &s, &e, &c);
graph[s].push_back({ e, c });
graph[e].push_back({ s, c });
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
road[i][j] = inf;
for (long long i = 1; i <= n; i++) dijk(i);
printf("%lld", ans());
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |