Cod sursa(job #979724)

Utilizator manutrutaEmanuel Truta manutruta Data 2 august 2013 16:43:33
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
//#include <windows.h>
using namespace std;

# define MAXN 103
//# define cout g

ifstream f("borcane.in");
ofstream g("borcane.out");

struct borcan {
    int id, nr;
};

int n, k;
borcan borcane[MAXN];

inline bool cmp (borcan a, borcan b) {
    return a.nr > b.nr;
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> borcane[i].nr;
        borcane[i].id = i;
    }

    sort (borcane + 1, borcane + n + 1, cmp);

    int j = 1, k = 2, l = 3;

    while (borcane[1].nr != 0 && borcane[2].nr != 0) {
        while (j != k && j != l && k != l) {
            for (int i = 1; i <= borcane[j].nr && i <= borcane[k].nr; i++) {
                g << borcane[j].id << ' ' << borcane[k].id << ' ' << borcane[l].id << '\n';
            }
            if (borcane[j].nr > borcane[k].nr) {
                borcane[l].nr += 2 * borcane[k].nr;
                borcane[j].nr -= borcane[k].nr;
                borcane[k].nr = 0;
                k = l;
            } else if (borcane[j].nr < borcane[k].nr) {
                borcane[l].nr += 2 * borcane[j].nr;
                borcane[k].nr -= borcane[j].nr;
                borcane[j].nr = 0;
                j = l;
            } else {
                borcane[l].nr += 2 * borcane[k].nr;
                borcane[j].nr = 0;
                borcane[k].nr = 0;
                k = l;
                j = l + 1;
                l++;

            }
            l++;
            if (l > n) {
                l = n;
            }

        }
        sort (borcane + 1, borcane + n + 1, cmp);
        k=1;
        j=2;
        l=3;
        /*for (int i = 1; i <= n; i++)
            cout<<borcane[i].nr<<' ';
        cout<<"\n";*/

        //system("pause");
    }

    return 0;
}