Submission #308855

#	Time	Username	Problem	Language	Result	Execution time	Memory
308855		talant117408	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	3 ms	4224 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 1e5+7;
const ll INF = 9e18;
vector <pii> dis(N, {INF, INF});
vector <vector <pii>> graph(N);

void dijkstra(int p){
    dis[p].second = 0;
    dis[p].first = 0;
    
    priority_queue <pii> K;
    K.push(mp(0, p));
    
    while(K.size()){
        auto v = K.top(); K.pop();
        v.first *= -1;
        if(v.first > dis[v.second].second) continue;
        for(auto to : graph[v.second]){
            if(v.first+to.second < dis[to.first].second){
                if(v.first+to.second < dis[to.first].first){
                    dis[to.first].second = dis[to.first].first;
                    dis[to.first].first = v.first+to.second;
                }
                else{
                    dis[to.first].second = v.first+to.second;
                }
                if(dis[to.first].second != INF){
                    K.push(mp(-dis[to.first].second, to.first));
                }
            }
        }
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    int i;
    for(i = 0; i < m; i++){
        graph[r[i][0]].pb(mp(r[i][1], (ll)l[i]));
        graph[r[i][1]].pb(mp(r[i][0], (ll)l[i]));
    }
    
    for(i = 0; i < k; i++){
        dijkstra(p[i]);
    }
    
    return dis[0].second;
}

/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

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