| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1057709 | 2024-08-14T03:56:26 Z | DucNguyen2007 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
struct duongdi
{
int u;
ll w;
bool operator < (const duongdi &o)const
{
return w>o.w;
}
};
pll d[maxN+1];
vector<duongdi> adj[maxN+1];
priority_queue<duongdi> pq;
ll travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
for(int i=0;i<M;i++)
{
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
for(int i=0;i<N;i++)
{
d[i]={inf,inf};
}
for(int i=0;i<K;i++)
{
pq.push({P[i],0});
d[P[i]]={0,0};
}
while(!pq.empty())
{
duongdi tmp=pq.top();
pq.pop();
int u=tmp.u;
ll w=tmp.w;
//cout<<u<<" "<<w<<'\n';
if(d[u].fi<w)
{
continue;
}
for(auto i:adj[u])
{
int v=i.u;
//cout<<1<<" "<<v<<" ";
if(d[v].fi>d[u].fi+i.w)
{
d[v].fi=d[u].fi+i.w;
if(d[v].se>d[u].fi+i.w)
{
swap(d[v].se,d[v].fi);
}
if(d[v].fi<inf)
{
pq.push({v,d[v].fi});
}
}
//cout<<d[v].fi<<'\n';
}
}
return d[0].fi;
}