Submission #306069

#	Time	Username	Problem	Language	Result	Execution time	Memory
306069		vipghn2003	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	795 ms	63976 KiB

crocodile

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=1e5+5;
long long d[N][2];
vector<pii>adj[N];

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
    for(int i=0;i<M;i++)
    {
        int u=R[i][0];
        int v=R[i][1];
        int w=L[i];
        adj[u].push_back(mp(v,w));
        adj[v].push_back(mp(u,w));
    }
    priority_queue<pair<int,long long>,vector<pair<int,long long>>,greater<pair<int,long long>>>pq;
    for(int i=0;i<N;i++) d[i][0]=d[i][1]=1e18;
    for(int i=0;i<K;i++)
    {
        d[P[i]][0]=d[P[i]][1]=0;
        pq.push(mp(0,P[i]));
    }
    while(!pq.empty())
    {
        int u=pq.top().se;
        long long dist=pq.top().fi;
        pq.pop();
        if(d[u][1]!=dist) continue;
        for(auto&v:adj[u])
        {
            long long ndist=dist+v.se;
            if(d[v.fi][0]>=ndist)
            {
                d[v.fi][1]=d[v.fi][0];
                d[v.fi][0]=ndist;
                pq.push(mp(d[v.fi][1],v.fi));
            }
            else if(d[v.fi][1]>ndist)
            {
                d[v.fi][1]=ndist;
                pq.push(mp(d[v.fi][1],v.fi));
            }
        }
    }
    return d[0][1];
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    int r[m][2],l[m],p[k];
    for(int i=0;i<m;i++) cin>>r[i][0]>>r[i][1];
    for(int i=0;i<m;i++) cin>>l[i];
    for(int i=0;i<k;i++) cin>>p[i];
    cout<<travel_plan(n,m,r,l,k,p);
}

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

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