Submission #565574

#	Time	Username	Problem	Language	Result	Execution time	Memory
565574		Uzouf	Evacuation plan (IZhO18_plan)	C++14	23 / 100	334 ms	32392 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=105;//2e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    int n,m; cin>>n>>m;
    vector<vector<pair<int,int> > > v(n+5);
    while (m--) {
      int a,b,c; cin>>a>>b>>c;
      v[a].push_back({c,b});
      v[b].push_back({c,a});
    }

    int k; cin>>k;
    int npp[k];
    for (int &i:npp) cin>>i;

    int dis[n+5];
    for (int i=0;i<n+5;i++) {
      dis[i]=1e10;
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

    for (int i:npp) {
      dis[i]=0; q.push({0,i});
    }

    while (!q.empty())
    {
        int cnt=q.top().first;
        int node=q.top().second;
        q.pop();
        if (dis[node]<cnt) {continue;}
        for (int i=0;i<v[node].size();i++)
        {
            int price=v[node][i].first;
            int child=v[node][i].second;
            if (dis[child]>(cnt+price))
            {
                dis[child]=(cnt+price);
                q.push({dis[child],child});
            }
        }
    }

    int t; cin>>t;
    while (t--) {
      int a,b; cin>>a>>b;
      cout<<min(dis[a],dis[b])<<endl;
    }

}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:46:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i=0;i<v[node].size();i++)
      |                      ~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46