Написать пост

День, магазин, парковка — задача для программистов

Аватар Евгений Туренко

Обложка поста День, магазин, парковка — задача для программистов

Дано

Парковка построена в виде графа. Он состоит из 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

Другие ограничения

Ограничение по времени: не более 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. Теперь этот блок заполнен.

 

Следите за новыми постами
Следите за новыми постами по любимым темам
11К открытий11К показов