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;
}
