oj.uz

Submission #970053

# Submission time Handle Problem Language Result Execution time Memory
970053 2024-04-26T07:25:49 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
0 / 100
 26 ms 12884 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<int,int>> edges[80001];
ll dist[80001];
bool vis[80001];
ll get(int pos,int target,ll curr) {
    if (curr == 0) {
        return 0;
    }
    curr = min(dist[pos],curr);
    vis[pos] = true;
    if (pos == target) {
        return curr;
    }
    ll maxi = 0;
    for (auto i:edges[pos]) {
        if (!vis[i.second]) {
            maxi = max(maxi,get(i.second,target,curr));
        }
    }
    return maxi;
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    for (int i=1;i<=80000;i++) {
        dist[i] = 1e18;
    }
    int n,m;
    cin >> n >> m;
    int x,y,d;
    for (int i=0;i<m;i++) {
        cin >> x >> y >> d;
        edges[x].push_back({d,y});
        edges[y].push_back({d,x});
    }
    int npp;
    cin >> npp;
    vector<ll> nppn(npp);
    for (int i=0;i<npp;i++) {
        cin >> x;
        nppn[i] = x;
        dist[x] = 0;
    }
    for (auto i:nppn) {
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        pq.push({0,i});
        while (!pq.empty()) {
            auto tmp = pq.top();
            pq.pop();
            if (tmp.first > dist[tmp.second]) {
                continue;
            }
            for (auto j:edges[tmp.second]) {
                if (dist[j.second] > tmp.first+j.first) {
                    dist[j.second] = tmp.first+j.first;
                    pq.push({dist[j.second],j.second});
                }
            }
        }
    }
    int c;
    cin >> c;
    for (int i=0;i<c;i++) {
        for (int j=1;j<=80000;j++) {
            vis[j] = false;
        }
        cin >> x >> y;
        cout << get(x,y,dist[x]) << '\n';
    }
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 12884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -