답안 #612218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612218	2022-07-29T11:40:58 Z	jame0313	Price List (POI13_cen)	C++17	100 / 100	158 ms	15656 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, mp2;
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]) {
            vector<int> t;
            for (auto nnx : mp2[nx]) {
                if (vis2[nnx] == x){
                    t.push_back(nnx);
                    continue;
                }
                vis2[nnx] = x;
                if (!vis[nnx] && dist[nnx] > dist[x] + B) {
                    dist[nnx] = dist[x] + B;
                    pq.push({dist[nnx], nnx});
                }
            }
            mp2[nx] = t;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> S >> A >> B;
    mp.resize(N + 1);
    mp2.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);
        mp2[a].push_back(b);
        mp2[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	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
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 #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2088 KB	Output is correct
2	Correct	10 ms	2136 KB	Output is correct
3	Correct	55 ms	2008 KB	Output is correct
4	Correct	12 ms	2004 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	6476 KB	Output is correct
2	Correct	38 ms	6448 KB	Output is correct
3	Correct	34 ms	4556 KB	Output is correct
4	Correct	38 ms	6048 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	10852 KB	Output is correct
2	Correct	52 ms	9424 KB	Output is correct
3	Correct	104 ms	10612 KB	Output is correct
4	Correct	124 ms	10220 KB	Output is correct
5	Correct	85 ms	11608 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	12824 KB	Output is correct
2	Correct	58 ms	9712 KB	Output is correct
3	Correct	115 ms	10788 KB	Output is correct
4	Correct	96 ms	10344 KB	Output is correct
5	Correct	74 ms	13120 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	14960 KB	Output is correct
2	Correct	107 ms	13420 KB	Output is correct
3	Correct	122 ms	11916 KB	Output is correct
4	Correct	137 ms	10268 KB	Output is correct
5	Correct	81 ms	14568 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	102 ms	13928 KB	Output is correct
2	Correct	85 ms	13964 KB	Output is correct
3	Correct	112 ms	12520 KB	Output is correct
4	Correct	98 ms	10444 KB	Output is correct
5	Correct	76 ms	15572 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	14448 KB	Output is correct
2	Correct	107 ms	14316 KB	Output is correct
3	Correct	158 ms	14368 KB	Output is correct
4	Correct	102 ms	10312 KB	Output is correct
5	Correct	92 ms	15656 KB	Output is correct

답안 #612218

Compilation message