oj.uz

답안 #917135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917135 2024-01-27T09:44:06 Z dilanyan Evacuation plan (IZhO18_plan) C++17
10 / 100
 4000 ms 27084 KB 
//-------------dilanyan------------\\ 
 
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
 
//------------------KarginDefines--------------------\\ 
 
#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
#define Kargin ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Usaco freopen(".in", "r", stdin); freopen(".out", "w", stdout);
 
 
//-------------------KarginConstants------------------\\ 
 
const ll mod = 1000000007;
const ll inf = 1e9 + 15;
 
//-------------------KarginCode------------------------\\ 
 
const int N = 100005;

int n;

vector<pair<int, int>> g[N];
int dist[N];

void dijikstra(int s) {
    pqueue<pair<int, int>> pq;
    vector<bool> vis(n + 1, false);
    vector<int> d(n + 1, inf);
    d[s] = 0;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto it : g[u]) {
            int v = it.first, w = it.second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({ -d[v],v });
            }
        }
    }
    for (int i = 1;i <= n;i++) dist[i] = min(dist[i], d[i]);
}

void KarginSolve() {
    int m;
    cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({ v,w }), g[v].pb({ u,w });
    }
    int k; cin >> k;
    fill(dist + 1, dist + n + 1, inf);
    for (int i = 0; i < k;i++) {
        int u; cin >> u;
        dijikstra(u);
    }
    int q; cin >> q;
    for (int i = 0;i < q;i++) {
        int s, t;
        cin >> s >> t;
        cout << min(dist[s], dist[t]) << '\n';
    }
}
 
int main() {
    //Usaco
    Kargin;
    int test = 1;
    //cin >> test;
    while (test--) {
        KarginSolve();
    }
    return 0;
}

Compilation message

plan.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //-------------dilanyan------------\\
      | ^
plan.cpp:8:1: warning: multi-line comment [-Wcomment]
    8 | //------------------KarginDefines--------------------\\
      | ^
plan.cpp:22:1: warning: multi-line comment [-Wcomment]
   22 | //-------------------KarginConstants------------------\\
      | ^
plan.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | //-------------------KarginCode------------------------\\
      | ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 4 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 10 ms 2908 KB Output is correct
6 Correct 56 ms 3084 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 3032 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 52 ms 3076 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 2 ms 2908 KB Output is correct
13 Correct 8 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 4 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 10 ms 2908 KB Output is correct
6 Correct 56 ms 3084 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 3032 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 52 ms 3076 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 2 ms 2908 KB Output is correct
13 Correct 8 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 220 ms 10144 KB Output is correct
17 Correct 246 ms 27084 KB Output is correct
18 Correct 24 ms 5212 KB Output is correct
19 Correct 190 ms 11108 KB Output is correct
20 Correct 235 ms 27076 KB Output is correct
21 Execution timed out 4005 ms 14728 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 14084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 4 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 10 ms 2908 KB Output is correct
6 Correct 56 ms 3084 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 3032 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 52 ms 3076 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 2 ms 2908 KB Output is correct
13 Correct 8 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 220 ms 10144 KB Output is correct
17 Correct 246 ms 27084 KB Output is correct
18 Correct 24 ms 5212 KB Output is correct
19 Correct 190 ms 11108 KB Output is correct
20 Correct 235 ms 27076 KB Output is correct
21 Execution timed out 4005 ms 14728 KB Time limit exceeded
22 Halted 0 ms 0 KB -