oj.uz

Submission #81117

# Submission time Handle Problem Language Result Execution time Memory
81117 2018-10-23T19:54:10 Z ToadDaveski Evacuation plan (IZhO18_plan) C++14
23 / 100
 1396 ms 31852 KB 
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
using namespace std;
vector <pair <ll,ll> > v[100001];
ll dp[100001];
priority_queue <pair <ll,ll> > q;
int main()
{
    ll n,m,Q,k,i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        dp[i]=1e9;
    for(i=1;i<=m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    cin>>k;
    for(i=1;i<=k;i++)
    {
        ll x,y;
        cin>>x;
        q.push({0,x});
        dp[x]=0;
    }
    while(!q.empty())
    {
        ll from=q.top().sc;
        ll weight=-q.top().fr;
        q.pop();
        if (dp[from]<weight)
            continue;
        for(auto to : v[from])
        {
            if (dp[to.fr]>dp[from]+to.sc)
            {
                dp[to.fr]=dp[from]+to.sc;
                q.push({-(dp[from]+to.sc),to.fr});
            }
        }
    }
    /*for(i=1;i<=n;i++)
    cout<<dp[i]<<" ";
    return 0;*/
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        ll x,y;
        cin>>x>>y;
        cout<<min(dp[x],dp[y])<<endl;
    }
    return 0;
}
/*
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


*/

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:25:14: warning: unused variable 'y' [-Wunused-variable]
         ll x,y;
              ^
plan.cpp:11:18: warning: unused variable 'j' [-Wunused-variable]
     ll n,m,Q,k,i,j;
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 9 ms 2680 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 9 ms 2680 KB Output is correct
6 Correct 9 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 9 ms 2808 KB Output is correct
10 Correct 9 ms 2680 KB Output is correct
11 Correct 9 ms 2808 KB Output is correct
12 Correct 9 ms 2808 KB Output is correct
13 Correct 9 ms 2680 KB Output is correct
14 Correct 9 ms 2680 KB Output is correct
15 Correct 9 ms 2780 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 9 ms 2680 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 9 ms 2680 KB Output is correct
6 Correct 9 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 9 ms 2808 KB Output is correct
10 Correct 9 ms 2680 KB Output is correct
11 Correct 9 ms 2808 KB Output is correct
12 Correct 9 ms 2808 KB Output is correct
13 Correct 9 ms 2680 KB Output is correct
14 Correct 9 ms 2680 KB Output is correct
15 Correct 9 ms 2780 KB Output is correct
16 Correct 575 ms 9656 KB Output is correct
17 Correct 1396 ms 31684 KB Output is correct
18 Correct 109 ms 5388 KB Output is correct
19 Correct 588 ms 11240 KB Output is correct
20 Correct 1388 ms 31716 KB Output is correct
21 Correct 813 ms 16500 KB Output is correct
22 Correct 556 ms 9208 KB Output is correct
23 Correct 1360 ms 31508 KB Output is correct
24 Correct 1366 ms 31768 KB Output is correct
25 Correct 1364 ms 31852 KB Output is correct
26 Correct 573 ms 11236 KB Output is correct
27 Correct 579 ms 11272 KB Output is correct
28 Correct 576 ms 11208 KB Output is correct
29 Correct 575 ms 11168 KB Output is correct
30 Correct 581 ms 11180 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 9 ms 2680 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 9 ms 2680 KB Output is correct
6 Correct 9 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 9 ms 2808 KB Output is correct
10 Correct 9 ms 2680 KB Output is correct
11 Correct 9 ms 2808 KB Output is correct
12 Correct 9 ms 2808 KB Output is correct
13 Correct 9 ms 2680 KB Output is correct
14 Correct 9 ms 2680 KB Output is correct
15 Correct 9 ms 2780 KB Output is correct
16 Correct 575 ms 9656 KB Output is correct
17 Correct 1396 ms 31684 KB Output is correct
18 Correct 109 ms 5388 KB Output is correct
19 Correct 588 ms 11240 KB Output is correct
20 Correct 1388 ms 31716 KB Output is correct
21 Correct 813 ms 16500 KB Output is correct
22 Correct 556 ms 9208 KB Output is correct
23 Correct 1360 ms 31508 KB Output is correct
24 Correct 1366 ms 31768 KB Output is correct
25 Correct 1364 ms 31852 KB Output is correct
26 Correct 573 ms 11236 KB Output is correct
27 Correct 579 ms 11272 KB Output is correct
28 Correct 576 ms 11208 KB Output is correct
29 Correct 575 ms 11168 KB Output is correct
30 Correct 581 ms 11180 KB Output is correct
31 Incorrect 4 ms 2652 KB Output isn't correct
32 Halted 0 ms 0 KB -