Cow Jogging

Soru Metni:

Sarikiz fazla kilolarindan kurtulmak icin, tepedeki ahirindan, gole kadar

yuruyus yapmak istiyor. Yuruyus sirasinda hep asagiya inecek ve geri

donerken de sallana sallana gelecek. Sarikiz sikilmamak icin hep ayni

yoldan gitmek istemiyor ayrica cok fazla yurumek istemedigi icin de

uzun yollari kullanmak istemiyor.

Ciftlikte toplam M (1 <= M <= 10,000) adet patika var. Bu patikalar otlaklari

birbirine bagliyor. Sirayla 1..N (1 <= N <= 1000) olarak numaralandirilmislar.

Bu numuralandirma yapilirken eger X>Y ise, otlak X'ten otlay Y'ye giden patika

yokul asagi. Otlak N en tepede ve Sarikiz'in yuruyuse baslayacagi ahir burada,

gol otlak 1'de bulunuyor. Otlak 1 en asagida.

Sarikiz'a otlak N'den otlak 1'e giden en kisa K (1 <= K <= 100) yolun uzunlugunu

hesaplamasi konusunda yardimci olunuz. Eger iki yol farkli patika dizilerinden

olusuyorsa farkli kabul ediliyorlar. Size X_i'den Y_i'ye giden patikalarin listesi

uzunluklari ile birlikte verilecek: (X_i, Y_i, D_i) (1 <= Y_i < X_i; Y_i < X_i <= N),

D_i (1 <= D_i <= 1,000,000).

SORUNUN ISMI: cowjog

GIRDI BICIMI:

* Satir 1: Boslukla ayrilmis uc tamsayi: N, M, ve K

* Satirlar 2..M+1: Satir i+1 yokus asagi bir yolu uc tamsayi ile tarif ediyor:

                               X_i, Y_i, ve D_i

ORNEK GIRDI (dosya cowjog.in):

5 8 7

5 4 1

5 3 1

5 2 1

5 1 1

4 3 4

3 1 1

3 2 1

2 1 1

GIRDI BICIMI:

* Satirlar 1..K: Satir i, i'inci en kisa yolun uzunlugunu iceriyor. Eger boyle bir yol

               mevcut degilse -1. Eger birden fazla en kisa yolun uzunlugu ayni ise, bu uzunlugun

               her yol icin ayri yazilmasi gerekiyor.

ORNEK CIKTI (dosya cowjog.out):

1

2

2

3

6

7

-1

CIKTININ ACIKLAMASI:

Yollar (5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1), (5-4-3-2-1).

Link: http://cerberus.delosent.com:790/MAR08

Çözüm:

Bize cycle olmayan bir graph verilmiş ve bu graph taki node lar zaten sıralı olduğu için dynamic programming güzel bir yaklaşım olur.

Varsayın ki i>=1 olmak üzere bütün i’ler için o node a ulaşan en kısa K yolu biliyoruz. Bu durumda (i-1). node a ulaşan en kısa K yolu bulmak için bu node una giren kenarları göz önünde bulundurmamız gerekiyor. Bu node a giren kenarların sayısı d olsun. Zaten d kenarın diğer ucundaki node lar için en kısa K yolu hesapladığımız için d*K yol içinden en kısa K tanesi (i-1). node a ulaşan en kısa  K yol olmuş olacaktır. Yöntemimiz her node için d*K zamana ihtiyaç duymaktadır ve graph ın genelinde bu rakam O(M*K) ya eşit olacaktır. M=10,000 ve K=100 olduğu için toplam işlem sayısı 1,000,000 dur yani çalışıyor.

Çözüm Kodu:

#include <stdio.h>

const int BIG = 1000000000;

const int MAXN = 2000;

const int MAXE = 20000;

const int MAXK = 200;

int n,e,k;

int ea[MAXE];

int eb[MAXE];

int elen[MAXE];

int d[MAXN];

int *out[MAXN];

int *len[MAXN];

int path[MAXN][MAXK];

int ei[MAXN];

int main() {

  FILE *fin;

  fin = fopen("cowjog.in", "r");

  fscanf(fin, "%d %d %d", &n, &e, &k);

  for(int i = 0; i < n; ++i){

    d[i] = 0;

  }

  for(int i = 0; i < e; ++i){

    int a,b,l;

    fscanf(fin, "%d %d %d", &b, &a, &l);

    --a; --b;

    ++d[a];

  }

  fclose(fin);

  out[0] = &eb[0];

  len[0] = &elen[0];

  for(int i = 1; i < n; ++i){

    out[i] = out[i-1] + d[i-1];

    len[i] = len[i-1] + d[i-1];

  }

  fin = fopen("cowjog.in", "r");

  fscanf(fin, "%d %d %d", &n, &e, &k);

  for(int i = 0; i < n; ++i){

    d[i] = 0;

  }

  for(int i = 0; i < e; ++i){

    int a,b,l;

    fscanf(fin, "%d %d %d", &b, &a, &l);

    --a; --b;

    out[a][d[a]] = b;

    len[a][d[a]] = l;

    ++d[a];

  }

  fclose(fin);

  path[n-1][0] = 0;

  for(int i = 1; i < k; ++i){

    path[n-1][i] = BIG;

  }

  for(int i = n-2; i >= 0; --i){

    for(int j = 0; j < d[i]; ++j){

      ei[j] = 0;

    }

    for(int j = 0; j < k; ++j){

      int best_m = 0;

      int best_d = BIG;

      for(int m = 0; m < d[i]; ++m){

               if(len[i][m] + path[out[i][m]][ei[m]] < best_d) {

                 best_m = m;

                 best_d = len[i][m] + path[out[i][m]][ei[m]];

               }

      }

      path[i][j] = best_d;

      ++ei[best_m];

    }

  }

  FILE *fout = fopen("cowjog.out", "w");

  for(int i = 0; i < k; ++i){

    fprintf(fout, "%d\n", (path[0][i] == BIG) ? -1 : path[0][i]);

  }

  fclose(fout);

  return(0);

}

Here is a concise solution that France's Louis Jachiet thinks might be easier to understand:

#include <stdio.h>

#include <algorithm>

#include <vector>

using namespace std;

int nb_paturages, nb_chemins, nb_itineraires;

vector<int> plus_court[1001];

vector<int> suiv      [1001];

vector<int> poids     [1001];

int main() {

    freopen("cowjog.in","r",stdin);

    freopen("cowjog.out","w",stdout);

    scanf( "%d %d %d", &nb_paturages, &nb_chemins, &nb_itineraires);

    // making the reverse graph

    for (int chem = 0; chem < nb_chemins ; chem++) {

        int dep, arr, pds;

        scanf ("%d %d %d", &dep, &arr, &pds);

        suiv [arr].push_back (dep);

        poids[arr].push_back (pds);

    }

    plus_court[1].push_back (0);

    for (int pat = 1; pat <= nb_paturages ; pat++) {

        sort (plus_court[pat].begin(), plus_court[pat].end());

        // exploring the current node for all  the shortest path

        for (int id = 0; id < plus_court[pat].size() &&

                                                             id < nb_itineraires; id++) {

            int tps = plus_court[pat][id];

            for (int id1 = 0; id1 < suiv[pat].size() ; id1++)

                plus_court[suiv[pat][id1]].push_back (tps + poids[pat][id1]);

        }

        // printing all the shortest path

        if (pat == nb_paturages)

            for (int id = 0; id < nb_itineraires ; id++)

                if (id < plus_court[pat].size())

                    printf ("%d\n", plus_court[pat][id]);

                            else

                    printf ("-1\n");

            plus_court[pat].clear();

    }

    return 0;

}