Submission #1288472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288472		nemkho	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	4 ms	8248 KiB

crocodile

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pr pair <ll, int>
using namespace std;
const int N = 2e5 + 5;
int n, m, r, val[N];
vector <pr> a[N];
ll d[N][2];
//void inp()
//{
//    cin >> n >> m >> r;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y;
//        ll w;
//        cin >> x >> y >> w;
//        x++;
//        y++;
//        a[x].push_back({w, y});
//        a[y].push_back({w, x});
//    }
//    for (int i = 1; i <= r; i++)
//    {
//        cin >> val[i];
//        val[i]++;
//    }
//}
void dijkstra ()
{
    priority_queue <pr, vector <pr>, greater <pr>> q;
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= r; i++)
    {
        q.push({0, val[i]});
        d[val[i]][0] = d[val[i]][1] = 0;
    }
    while (!q.empty())
    {
        int u = q.top().se;
        ll k = q.top().fi;
        q.pop();
        if (k > d[u][1])
            continue;
        for (pr i : a[u])
        {
            int v = i.se;
            ll sum = d[u][1] + i.fi;
            if (sum < d[v][0])
            {
                d[v][1] = d[v][0];
                d[v][0] = sum;
                q.push({d[v][0], v});
                q.push({d[v][1], v});
            }
            else if (sum < d[v][1])
            {
                d[v][1] = sum;
                q.push({d[v][1], v});
            }
        }
    }
}
//void solve()
//{
//    dijkstra();
//    cout << d[1][1];
//}
ll travel_plan (int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;
    m = M;
    r = K;
    for (int i = 0; i < m; i++)
    {
        a[R[i][0]+1].push_back({L[i], R[i][1]+1});
        a[R[i][1]+1].push_back({L[i], R[i][0]+1});
    }
    for (int i = 0; i < K; i++)
        val[i+1] = P[i] + 1;
    dijkstra();
    return d[1][1];
}
//int main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("TEST.INP","r",stdin);
//    freopen("TEST.OUT","w",stdout);
//    inp();
//    solve();
//}

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