제출 #1288475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288475		nemkho	악어의 지하 도시 (IOI11_crocodile)	C++17	89 / 100	392 ms	80964 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], tmp[N];
vector <pr> a[N];
ll d[N][2];
int e[N][2], W[N];
//void inp()
//{
//    cin >> n >> m >> r;
//    for (int i = 0; i < m; i++)
//    {
//        int x, y;
//        ll w;
//        cin >> e[i][0] >> e[i][1];
//    }
//    for (int i = 0; i < m; i++)
//        cin >> W[i];
//    for (int i = 0; i < r; i++)
//    {
//        cin >> tmp[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 = k + i.fi;
            if (sum < d[v][0])
            {
                d[v][1] = d[v][0];
                d[v][0] = sum;
                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++)
    {
        //cout << L[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();
//    cout << travel_plan(n, m, e, W, r, tmp);
//}

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