# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244549 | arnold518 | Price List (POI13_cen) | C++14 | 160 ms | 14168 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const ll INF = 1e15;
int N, M, K, A, B;
pii E[MAXN+10];
vector<int> adj[MAXN/2+10], adj2[MAXN/2+10];
ll dist1[MAXN+10], dist2[MAXN+10];
bool vis1[MAXN+10], vis2[MAXN+10];
struct Queue
{
int v, w;
};
bool f(int u, int v) { return binary_search(adj2[u].begin(), adj2[u].end(), v); }
int main()
{
int i, j;
scanf("%d%d%d%d%d", &N, &M, &K, &A, &B);
for(i=1; i<=M; i++)
{
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
adj2[u].push_back(v);
adj2[v].push_back(u);
}
for(i=1; i<=N; i++) sort(adj2[i].begin(), adj2[i].end());
for(i=1; i<=N; i++) dist1[i]=dist2[i]=INF;
queue<Queue> Q;
Q.push({K, 0}); vis1[K]=1; dist1[K]=0;
while(!Q.empty())
{
Queue now=Q.front(); Q.pop();
for(auto nxt : adj[now.v])
{
if(vis1[nxt]) continue;
dist1[nxt]=now.w+1;
vis1[nxt]=true;
Q.push({nxt, now.w+1});
}
}
Q.push({K, 0}); vis2[K]=1; dist2[K]=0;
while(!Q.empty())
{
Queue now=Q.front(); Q.pop();
for(auto nxt : adj[now.v])
{
for(auto &nxt2 : adj[nxt])
{
if(vis2[nxt2])
{
nxt2=-1;
continue;
}
if(f(now.v, nxt2)) continue;
Q.push({nxt2, now.w+1});
dist2[nxt2]=now.w+1;
vis2[nxt2]=true;
}
vector<int> V;
for(auto it : adj[nxt]) if(it!=-1) V.push_back(it);
swap(adj[nxt], V);
}
}
for(i=1; i<=N; i++)
{
if(dist1[i]%2==0) printf("%lld\n", min(dist1[i]*A, dist1[i]/2*B));
else printf("%lld\n", min({dist1[i]*A, dist1[i]/2*B+A, dist2[i]*B}));
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |