Парковка построена в виде графа. Он состоит из N узлов и M рёбер. В нём нет ни петель, ни параллельных рёбер.
Каждый узел — парковочный блок с определённой вместимостью.
Каждое ребро (u, v) обладает весом w. Это означает, что чтобы добраться от узла u к узлу v, надо потратить некоторое количество единиц w.
Места на парковке платные, стоимость составляет F единиц в любом месте графа.
На парковку въезжает K одинаковых автомобилей, каждый из которых отмечен номером от 1 до K. Машины въезжают в стандартном порядке: сначала автомобиль под номером 1, затем — под номером 2 и так далее до автомобиля под номером K.
Нужно распечатать чек с минимальной общей суммой расходов для владельца автомобиля. Сумма расходов складывается из парковочного взноса и затрат на перемещение (W, вы же помните?). Гарантируется, что из одного парковочного места можно добраться до любого другого.
Все автомобили въезжают на стоянку с первого парковочного места.
Формат ввода
Первая строка состоит из трёх целых чисел: N, M и F. Они обозначают количество узлов, рёбер и стоимость за въезд соответственно.
Вторая строка состоит из N целых чисел, разделённых пробелами, которые означают количество мест в каждом блоке парковки. Этот массив представляется как C[].
Следующие строки M содержат три целых числа, разделённых пробелом: u, v и w, обозначающие, что чтобы добраться от узла u к узлу v будет затрачено w единиц.
Последняя строка содержит целое число K.
Пример ввода:
5 4 201 2 1 1 21 2 24 5 13 4 11 3 15
Формат вывода
Выведите K целых чисел, разделённых пробелами, обозначающие ответ для каждого автомобиля. i-е целое число из ряда целых чисел, разделённых пробелами, означает ответ для i-го номера автомобиля.
Пример: есть пять автомобилей. Третье целое число в ряду из пяти будет соответствовать третьему автомобилю.
Если автомобиль невозможно припарковать, выведите -1 для него.
Пример вывода:
20 21 22 22 22
Ограничения для входных данных
Другие ограничения
Ограничение по времени: не более 1 секунды для каждого входного файла. Ограничение в потреблении памяти: 256 MB. Ограничение для исходного кода: 1024 KB.
Ниже представлены решения на различных языках, а в конце дано пояснение. Делитесь своими решениями в комментариях.
Варианты решения
C++
#include <bits/stdc++.h>
#define need_for_insane_speed \
ios::sync_with_stdio(false); \
cin.tie(NULL);
#define endl '\n'
using namespace std;
int main()
{
need_for_insane_speed;
long n, m, f, k, i, a, b, c;
pair<long, long> tmp;
vector< vector< pair<long, long> > > adj;
vector<bool> vis;
vector<long> ans, val;
priority_queue<pair<long, long>, vector< pair<long, long> >, greater< pair<long, long> > > pq;
cin >> n >> m >> f;
vector< vector< pair<long, long> > >(n+1).swap(adj);
vector<bool>(n+1, false).swap(vis);
vector<long>(n+1).swap(val);
i=1;
while(i<=n)
cin >> val[i++];
i=0;
while(i<m)
{
cin >> a >> b >> c;
adj[a].push_back(make_pair(c, b));
adj[b].push_back(make_pair(c, a));
i++;
}
cin >> k;
vector<long>(k+1, -1).swap(ans);
pq.push(make_pair(0, 1));
i = 1;
while((i<=k) && (!pq.empty()))
{
tmp = pq.top();
pq.pop();
a = tmp.second;
b = tmp.first;
if(!vis[a])
{
vis[a] = true;
while((i<=k) && (val[a]--))
{
ans[i] = b + f;
i++;
}
for(c=0;c<adj[a].size();c++)
if(!vis[adj[a][c].second])
pq.push(make_pair(adj[a][c].first+b, adj[a][c].second));
}
}
for(i=1;i<=k;i++)
cout << ans[i] << ' ';
cout << endl;
return 0;
}
C++ 14
#include<bits/stdc++.h>
#include <boost/functional/hash.hpp>
#include <unordered_map>
//unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m;
using namespace std;
typedef long ll;
const ll mod=1e15;
#define se second
#define fi first
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define itr(it,l,x) for(auto it=l[x].begin();it!=l[x].end();it++)
#define go(it,mp) for(auto it=mp.begin();it!=mp.end();it++)
ll domod(ll m,ll k)
{if(m>k)return m-k;}
#define f(i,a,b) for(i=a;i<b;i++)
template <typename T> /*use iff inputs >0*/
inline void in(T &a) {
register T c;
a = 0;
do c = getchar_unlocked(); while(c < '0');
do {
a = (a << 1) + (a << 3) + c - '0';
c = getchar_unlocked();
} while (c >= '0');
}
ll read () { /*use for all cases but is slightly slower than above*/
bool minus = false;
ll result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
template <typename T>
inline void pr(T a) {
char s[11];
T t = -1;
do {
s[++t] = a % 10 + '0';
a /= 10;
} while (a > 0);
while (t >= 0) putchar_unlocked(s[t--]);
putchar_unlocked(' ');
}
struct node
{
ll val,indx;
}a[100001];
ll n;
ll track[100001];
void build()
{
ll i,c,p;
f(i,0,n)
{
c=i;
p=(c-1)/2;
track[i]=i;
while((c)&&(a[p].val>a[c].val))
{
swap(a[p],a[c]);
track[a[p].indx]=p;
track[a[c].indx]=c;
c=p;
p=(c-1)/2;
}
}
}
void update()
{
ll lc,rc,p;
p=0;
lc=1;
rc=2;
while(((lc<n)&&(a[p].val>a[lc].val))||((rc<n)&&(a[p].val>a[rc].val)))
{
if((lc<n)&&(a[p].val>a[lc].val))
{
if(rc<n)
{
if(a[lc].val<a[rc].val)
{
swap(a[p],a[lc]);
track[a[p].indx]=p;
track[a[lc].indx]=lc;
p=lc;
}
else
{
swap(a[p],a[rc]);
track[a[p].indx]=p;
track[a[rc].indx]=rc;
p=rc;
}
}
else
{
swap(a[p],a[lc]);
track[a[p].indx]=p;
track[a[lc].indx]=lc;
p=lc;
}
}
else if((rc<n)&&(a[p].val>a[rc].val))
{
swap(a[p],a[rc]);
track[a[p].indx]=p;
track[a[rc].indx]=rc;
p=rc;
}
lc=2*p+1;
rc=2*p+2;
}
}
void point(ll indx)
{
ll c,p;
c=indx;
p=(c-1)/2;
while((c)&&(a[p].val>a[c].val))
{
swap(a[p],a[c]);
track[a[p].indx]=p;
track[a[c].indx]=c;
c=p;
p=(c-1)/2;
}
}
struct edge
{
ll d,w;
};
struct h
{
ll ind,val;
};
bool cmp(h a1,h b1)
{
return a1.val<b1.val;
}
int main()
{
ll m,p,i,x,y,w,num;
in(n);
num=n;
in(m);
in(p);
ll b[n];
f(i,0,n)
in(b[i]);
list<edge>l[n];
edge q;
f(i,0,m)
{
in(x);
in(y);
in(w);
x--;
y--;
q={y,w};
l[x].pb(q);
q.d=x;
l[y].pb(q);
}
f(i,0,n)
a[i]={mod,i};
a[0].val=0;
build();
ll dis[n];
while(n)
{
ll xx=a[0].val;
ll yy=a[0].indx;
dis[yy]=xx;
track[a[0].indx]=-1;
track[a[n-1].indx]=0;
swap(a[0],a[n-1]);
n--;
update();
itr(it,l,yy)
{
ll indx=track[it->d];
if(indx!=-1)
{
ll u=xx+it->w;
if(u<a[indx].val)
{
a[indx].val=u;
point(indx);
}
}
}
}
in(x);
n=num;
h res[n];
f(i,0,n)
res[i]={b[i],dis[i]};
sort(res,res+n,cmp);
f(i,0,n)
{
while((res[i].ind>0)&&(x>0))
{
pr(p+res[i].val);
x--;
res[i].ind--;
}
if(x<=0)
break;
}
while(x>0)
{
printf("-1 ");
x--;
}
}
Java
import java.io.*;
import java.util.*;
import java.math.*;
class Parking {
public static void main(String args[]) {
try {
InputReader in = new InputReader(System.in);
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
int n = in.readInt();
int m = in.readInt();
int f = in.readInt();
Vector<Edge> graph[] = new Vector[n];
for (int i = 0; i < n; i++) {
graph[i] = new Vector<>();
}
int capacity[] = new int[n];
for (int i = 0; i < n; i++) {
capacity[i] = in.readInt();
}
for (int i = 0; i < m; i++) {
int u = in.readInt() - 1;
int v = in.readInt() - 1;
long c = in.readLong();
graph[u].add(new Edge(u, v, c));
graph[v].add(new Edge(v, u, c));
}
long cost[] = new long[n];
Arrays.fill(cost, Long.MAX_VALUE);
Queue<IndexValue> pq = new PriorityQueue<IndexValue>(100000, new Comparator<IndexValue>() {
@Override
public int compare(IndexValue o1, IndexValue o2) {
return Long.compare(o1.v, o2.v);
}
});
pq.add(new IndexValue(0, 0));
cost[0] = 0;
boolean vis[] = new boolean[n];
while(!pq.isEmpty()) {
IndexValue indexValue = pq.poll();
int ver = indexValue.index;
vis[ver] = true;
for (Edge e: graph[ver]) {
if (!vis[e.v] && cost[e.v] > cost[e.u] + e.c) {
cost[e.v] = cost[e.u] + e.c;
pq.add(new IndexValue(e.v, cost[e.v]));
}
}
}
CostIndex[] costIndices = new CostIndex[n];
for (int i = 0; i < n; i++) {
costIndices[i] = new CostIndex(i, cost[i]);
}
Arrays.sort(costIndices);
int index = 0;
int k = in.readInt();
long answers[] = new long[k];
for (int i = 0; i < k; i++) {
if (index >= costIndices.length) {
answers[i] = -1;
}
else {
long ans = costIndices[index].cost + f;
answers[i] = ans;
capacity[costIndices[index].index]--;
if (capacity[costIndices[index].index] == 0) {
index++;
}
}
}
for (int i = 0; i < k; i++) {
out.write(Long.toString(answers[i]) + " ");
}
out.close();
} catch (Exception e) {
e.printStackTrace();
}
}
private static class Edge {
int u, v;
long c;
public Edge(int u, int v, long c) {
this.u = u;
this.v = v;
this.c = c;
}
}
private static class CostIndex implements Comparable<CostIndex> {
int index;
long cost;
public CostIndex(int index, long cost) {
this.index = index;
this.cost = cost;
}
@Override
public int compareTo(CostIndex o) {
return Long.compare(this.cost, o.cost);
}
}
private static class IndexValue {
int index;
long v;
public IndexValue(int index, long v) {
this.index = index;
this.v = v;
}
}
}
class InputReader {
private boolean finished = false;
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int peek() {
if (numChars == -1)
return -1;
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
return -1;
}
if (numChars <= 0)
return -1;
}
return buf[curChar];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int length = readInt();
if (length < 0)
return null;
byte[] bytes = new byte[length];
for (int i = 0; i < length; i++)
bytes[i] = (byte) read();
try {
return new String(bytes, "UTF-8");
} catch (UnsupportedEncodingException e) {
return new String(bytes);
}
}
public static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private String readLine0() {
StringBuffer buf = new StringBuffer();
int c = read();
while (c != '\n' && c != -1) {
if (c != '\r')
buf.appendCodePoint(c);
c = read();
}
return buf.toString();
}
public String readLine() {
String s = readLine0();
while (s.trim().length() == 0)
s = readLine0();
return s;
}
public String readLine(boolean ignoreEmptyLines) {
if (ignoreEmptyLines)
return readLine();
else
return readLine0();
}
public BigInteger readBigInteger() {
try {
return new BigInteger(readString());
} catch (NumberFormatException e) {
throw new InputMismatchException();
}
}
public char readCharacter() {
int c = read();
while (isSpaceChar(c))
c = read();
return (char) c;
}
public double readDouble() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
return res * Math.pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
return res * Math.pow(10, readInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public boolean isExhausted() {
int value;
while (isSpaceChar(value = peek()) && value != -1)
read();
return value == -1;
}
public String next() {
return readString();
}
public boolean readBoolean() {
return readInt() == 1;
}
}
Java 8
import java.util.*;
import java.io.*;
import java.lang.*;
public class Solution {
static int[] c;
public static void main(String args[] ) {
InputReader fi=new InputReader(System.in);
PrintWriter printWriter=new PrintWriter(System.out);
int n,m,f,i,j,k,total;
n=fi.nextInt();
m=fi.nextInt();
f=fi.nextInt();
c=new int[n+1];
total=0;
for (i=1;i<=n;i++){
c[i]=fi.nextInt();
total+=c[i];
}
Graph g=new Graph(n,m);
for (i=0;i<m;i++){
g.addEdge(fi.nextInt(),fi.nextInt(),fi.nextLong());
}
PriorityQueue<Node> slots=g.Dijkstra(1);
k=fi.nextInt();
long ans[]=new long[k+1];
for (i=1;i<=Math.min(total,k) && !slots.isEmpty();i++){
Node x=slots.poll();
while (i<=Math.min(total,k) && c[x.vertex]>0){
ans[i]=f+x.cost;
i++;
c[x.vertex]--;
}
i--;
}
for (i=1;i<=k;i++){
if(ans[i]!=0) printWriter.print(ans[i] + " ");
else printWriter.print("-1" + " ");
}
printWriter.close();
}
}
class Graph{
int n,m;
ArrayList<Node>[] adj;
Graph(int n,int m){
this.n=n;
this.m=m;
adj=new ArrayList[n+1];
for (int i=0;i<=n ;i++ ) {
adj[i]=new ArrayList<Node>();
}
}
void addEdge(int i,int j,long weight){
adj[i].add(new Node(j,weight));
adj[j].add(new Node(i,weight));
}
PriorityQueue<Node> Dijkstra(int start){
long dis[]=new long[n+1];
Arrays.fill(dis,Long.MAX_VALUE);
dis[start]=0;
boolean [] vis=new boolean[n+1];
vis[start]=true;
PriorityQueue<Node> pq=new PriorityQueue<>();
pq.add(new Node(1,0));
while (!pq.isEmpty()){
Node temp=pq.poll();
for (Node x : adj[temp.vertex]){
if (dis[x.vertex] > dis[temp.vertex]+x.cost){
dis[x.vertex]=dis[temp.vertex]+x.cost;
pq.add(new Node(x.vertex,dis[x.vertex]));
}
}
}
PriorityQueue<Node> slots=new PriorityQueue<>();
for (int i=1;i<=n;i++){
slots.add(new Node(i,dis[i]));
}
return slots;
}
}
class Node implements Comparable<Node>{
int vertex;
long cost;
Node(int vertex, long cost){
this.vertex = vertex; this.cost = cost;
}
public int compareTo(Node x){
return Long.compare(this.cost, x.cost);
}
}
class InputReader {
InputStream stream;
byte[] buf = new byte[8192];
int curChar, snumChars;
SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n+1];
for (int i = 1; i <= n; i++)
a[i] = nextInt();
return a;
}
public String readString() {
int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
Объяснение
Автомобиль под номером 1 паркуется только в первом парковочном блоке. Таким образом, общая стоимость выглядит так: 0 + 20 = 20 (0, так как автомобиль парковался только в первом блоке). Теперь этот блок заполнен.
Автомобиль под номером 2 паркуется в блоке 3. Общая стоимость: 1 + 20 = 21 (1, так как чтобы добраться от первого до третьего блока нужно потратить 1 единицу). Теперь этот блок заполнен.
Автомобиль под номером 3 паркуется в блоке 2. Общая стоимость: 2 + 20 = 22.
Автомобиль под номером 4 паркуется в блоке 2. Общая стоимость: 2 + 20 = 22. Теперь этот блок заполнен.
Автомобиль под номером 5 паркуется в блоке 4. Общая стоимость: 2 + 20 = 22. Теперь этот блок заполнен.
Математика и компьютерные науки идут рука об руку. Подобрали 7 математических формул разного уровня сложности для проверки — сможете ли вы их реализовать? И на всякий случай снабдили статью нашими решениями.
