# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
611861 |
2022-07-29T08:11:05 Z |
jame0313 |
Price List (POI13_cen) |
C++17 |
|
4000 ms |
9452 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
vector<vector<int> > mp;
bool vis[100001];
int vis2[100001];
ll dist[100001];
const ll INF = 1LL << 60;
priority_queue<pll, vector<pll>, greater<pll> > pq;
int N, M, S, A, B;
void dijkstra() {
for (int i = 1; i <= N; i++) dist[i] = INF;
dist[S] = 0;
pq.push({dist[S], S});
while (!pq.empty()) {
auto [d, x] = pq.top();
pq.pop();
if (vis[x]) continue;
vis[x] = true;
vis2[x] = x;
for (auto nx : mp[x]) {
vis2[nx] = x;
if (!vis[nx] && dist[nx] > dist[x] + A) {
dist[nx] = dist[x] + A;
pq.push({dist[nx], nx});
}
}
for (auto nx : mp[x]) {
if(dist[nx]+A<dist[x]+B) continue;
for (auto nnx : mp[nx]) {
if (vis2[nnx] == x) continue;
vis2[nnx] = x;
if (!vis[nnx] && dist[nnx] > dist[x] + B) {
dist[nnx] = dist[x] + B;
pq.push({dist[nnx], nnx});
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> S >> A >> B;
mp.resize(N + 1);
vector<int> costs;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
mp[a].push_back(b);
mp[b].push_back(a);
}
dijkstra();
for (int i = 1; i <= N; i++) cout << dist[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
1396 KB |
Output is correct |
2 |
Correct |
6 ms |
1364 KB |
Output is correct |
3 |
Correct |
15 ms |
1364 KB |
Output is correct |
4 |
Correct |
13 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2254 ms |
3852 KB |
Output is correct |
2 |
Correct |
21 ms |
4212 KB |
Output is correct |
3 |
Correct |
22 ms |
2924 KB |
Output is correct |
4 |
Correct |
36 ms |
3916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2359 ms |
6172 KB |
Output is correct |
2 |
Correct |
31 ms |
5384 KB |
Output is correct |
3 |
Correct |
63 ms |
5708 KB |
Output is correct |
4 |
Correct |
51 ms |
6460 KB |
Output is correct |
5 |
Execution timed out |
4096 ms |
7464 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3753 ms |
7192 KB |
Output is correct |
2 |
Correct |
43 ms |
6144 KB |
Output is correct |
3 |
Correct |
76 ms |
6836 KB |
Output is correct |
4 |
Correct |
52 ms |
6516 KB |
Output is correct |
5 |
Execution timed out |
4065 ms |
8296 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2294 ms |
8536 KB |
Output is correct |
2 |
Correct |
55 ms |
8460 KB |
Output is correct |
3 |
Correct |
83 ms |
7492 KB |
Output is correct |
4 |
Correct |
48 ms |
6476 KB |
Output is correct |
5 |
Execution timed out |
4011 ms |
8984 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
602 ms |
7844 KB |
Output is correct |
2 |
Correct |
47 ms |
8776 KB |
Output is correct |
3 |
Correct |
57 ms |
7840 KB |
Output is correct |
4 |
Correct |
56 ms |
6644 KB |
Output is correct |
5 |
Execution timed out |
4059 ms |
9424 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
7928 KB |
Output is correct |
2 |
Correct |
57 ms |
7860 KB |
Output is correct |
3 |
Correct |
100 ms |
7860 KB |
Output is correct |
4 |
Correct |
57 ms |
6608 KB |
Output is correct |
5 |
Execution timed out |
4093 ms |
9452 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |