Submission #154844

#	Time	Username	Problem	Language	Result	Execution time	Memory
154844		davitmarg	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1576 ms	101924 KiB

crocodile

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;

// #ifndef death
//     #include "grader.h"
// #endif

int n,m,k,win[100005],p[100005],used[100005];
vector<pair<int,LL>> g[100005];
pair<LL,LL> dp[100005];

void add(pair<LL,LL> &p,LL val)
{
    if(val<=p.first)
    {
        p.second=p.first;
        p.first=val;
    }
    else if(p.second>val)
        p.second=val;
}

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
    n=N;
    m=M;
    k=K;
    for(int i=0;i<k;i++)
    {
        p[i+1]=P[i]+1;
        win[P[i]+1]=1;
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        LL d;
        a=R[i][0]+1;
        b=R[i][1]+1;
        d=L[i];

        if(win[a] && win[b])
            continue;

        g[a].PB(MP(b,d));
        g[b].PB(MP(a,d));
    }

    for(int i=1;i<=n;i++)
        dp[i]=MP(mod*mod,mod*mod);

    priority_queue<pair<LL,int>> q;
    for(int i=1;i<=k;i++)
    {
        q.push(MP(0,p[i]));
        dp[p[i]]=MP(0,0);
    }
    while(!q.empty())
    {
        int v=-1;
        do
        {
            v=q.top().second;
            q.pop();
        } while (used[v] && !q.empty());

        if(used[v] || v==-1)
            break;
        used[v]=1;
        //cout<<v<<" = "<<dp[v].second<<endl;
        for(int i=0;i<g[v].size();i++)
        {
            int to=g[v][i].first;
            LL d=g[v][i].second;
            add(dp[to],dp[v].second+d);
            q.push( MP(-dp[to].second,to) );
        }   
    }
    //cout<<dp[1].first<<" : "<<dp[1].second<<endl;
    return dp[1].second;
}

#ifdef death

int main()
{
    int N,M,K,R[102][2],P[102];
    int L[102];
    cin>>N>>M>>K;
    for(int i=0;i<M;i++)
        cin>>R[i][0]>>R[i][1]>>L[i];
    for(int i=0;i<K;i++)
        cin>>P[i];
    cout<<travel_plan(N,M,R,L,K,P);
	return 0;
}

#endif
 
/*

2
4 5
1 2



*/

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++)
                     ~^~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11