oj.uz

답안 #611805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
611805 2022-07-29T07:42:46 Z jame0313 Price List (POI13_cen) C++17
50 / 100
 4000 ms 9496 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]) {
            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';
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 1404 KB Output is correct
2 Correct 42 ms 1396 KB Output is correct
3 Correct 8 ms 1432 KB Output is correct
4 Correct 8 ms 1364 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2141 ms 4140 KB Output is correct
2 Correct 2060 ms 4156 KB Output is correct
3 Correct 25 ms 2892 KB Output is correct
4 Correct 36 ms 3940 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2233 ms 6820 KB Output is correct
2 Correct 671 ms 5956 KB Output is correct
3 Correct 46 ms 6692 KB Output is correct
4 Correct 47 ms 6560 KB Output is correct
5 Execution timed out 4049 ms 7372 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3572 ms 8064 KB Output is correct
2 Correct 140 ms 6076 KB Output is correct
3 Correct 54 ms 6768 KB Output is correct
4 Correct 57 ms 6504 KB Output is correct
5 Execution timed out 4021 ms 8268 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2391 ms 9376 KB Output is correct
2 Correct 622 ms 8400 KB Output is correct
3 Correct 83 ms 7472 KB Output is correct
4 Correct 47 ms 6496 KB Output is correct
5 Execution timed out 4030 ms 9052 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 607 ms 8732 KB Output is correct
2 Correct 574 ms 8708 KB Output is correct
3 Correct 67 ms 7764 KB Output is correct
4 Correct 41 ms 6620 KB Output is correct
5 Execution timed out 4045 ms 9436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 8952 KB Output is correct
2 Correct 49 ms 8908 KB Output is correct
3 Correct 69 ms 8864 KB Output is correct
4 Correct 43 ms 6600 KB Output is correct
5 Execution timed out 4066 ms 9496 KB Time limit exceeded
6 Halted 0 ms 0 KB -