Submission #26579

#TimeUsernameProblemLanguageResultExecution timeMemory
26579wwiiiii주유소 (KOI16_gas)C++14
100 / 100
1008 ms51900 KiB
#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)

gas.cpp: In function 'int main()':
gas.cpp:73:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
                            ^
gas.cpp:74:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (long long i = 1; i <= n; i++) scanf("%lld", &oil[i]);
                                                           ^
gas.cpp:77:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, c; scanf("%lld %lld %lld", &s, &e, &c);
                                                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...