Submission #1013489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013489		Error404	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	333 ms	81848 KiB

crocodile

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f first
#define s second
#define pi pair<ll,ll>
#define vi vector<ll>
#define vpi vector<pi>
#define pb push_back
#define INF 1e18
#define endl '\n'
//#define int ll
#define pii pair<pi,ll>

const int MAX = 1e5+1;

vpi g[MAX];
ll dis[MAX][2];


ll travel_plan(int n,int m, int R[][2], int L[],int k, int P[]){
    ll a,b,c,from;
    
    for(int i = 0; i < m; i++){
       a = R[i][0];
       b = R[i][1];
       c = L[i];
       g[a].pb({b,c});
       g[b].pb({a,c});
    }

    priority_queue<pi, vector<pi>, greater<pi>>pq;
     for(int i = 0; i < n; i++){
        dis[i][0]=INF;
        dis[i][1]=INF;
    }

    for(int i =0 ; i < k; i++){
        dis[P[i]][0]=0;
        dis[P[i]][1]=0;
        pq.push({0,P[i]});   
    }

   int vis[n];
   memset(vis,0,sizeof(vis));

    while(!pq.empty()){
        b = pq.top().f;
        from = pq.top().s;

        pq.pop();
        
        if(vis[from]) {
            continue;
        }
        vis[from]=1;
        for(pi i : g[from]){
            int to = i.f;
            int w= i.s;
      
            if(dis[to][0]> b+w){
                bool flag = false;
                if(dis[to][0]!=INF) flag = true;
                dis[to][1] = dis[to][0];
                dis[to][0] = dis[from][1]+w;
                if(flag)pq.push({dis[to][1], to});
            }
            else if(dis[to][1]>b+w){
                dis[to][1]=dis[from][1]+w;
                pq.push({dis[to][1], to});
            }
           
        }
       
    }

   
     return dis[0][1]; 

}

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