Ho risolto il problema “maree a Venezia” con questo codice
#include<stdio.h>
#include<stdlib.h>
struct nodo{
int num;
struct nodo* next;
};
int solve(int N, int M, int T, int* S, int* E) {
return solve2(N,M,T,S,E);
}
int solve2(int n, int m, int t, int* s, int* s2) {
struct nodo** adj = (struct nodo**)malloc(n*sizeof(struct nodo));
int i;
for(i=0; i<n; i++)
adj[i] = NULL;
struct nodo* e;
for(i=0; i<m; i++){
if(adj[s[i]] == NULL){
adj[s[i]] = (struct nodo*)malloc(sizeof(struct nodo));
adj[s[i]]->num = s2[i];
adj[s[i]]->next = NULL;
}
else{
e = (struct nodo*)malloc(sizeof(struct nodo));
e->num = s2[i];
e->next = adj[s[i]];
adj[s[i]] = e;
}
}
int tempi[n];
tempi[0] = 0;
for(i=1; i<n; i++)
tempi[i] = -1;
int cur;
struct nodo* inizio = (struct nodo*)malloc(sizeof(struct nodo));
inizio->num = 0;
inizio->next = NULL;
struct nodo* fine = inizio;
while(inizio != NULL){
cur = inizio->num;
inizio = inizio->next;
e = adj[cur];
while(e != NULL){
if(tempi[e->num] > tempi[cur]+1 || tempi[e->num] == -1){
tempi[e->num] = tempi[cur]+1;
if(inizio == NULL){
inizio = (struct nodo*)malloc(sizeof(struct nodo));
inizio->num = e->num;
inizio->next = NULL;
fine = inizio;
}
else{
fine->next = (struct nodo*)malloc(sizeof(struct nodo));
fine = fine->next;
fine->num = e->num;
fine->next = NULL;
}
}
e = e->next;
}
}
int tempi2[n];
tempi2[n-1] = 0;
for(i=0; i<n-1; i++)
tempi2[i] = -1;
inizio = (struct nodo*)malloc(sizeof(struct nodo));
inizio->num = n-1;
inizio->next = NULL;
fine = inizio;
while(inizio != NULL){
cur = inizio->num;
inizio = inizio->next;
e = adj[cur];
while(e != NULL){
if(tempi2[e->num] > tempi2[cur]+1 || tempi2[e->num] == -1){
tempi2[e->num] = tempi2[cur]+1;
if(inizio == NULL){
inizio = (struct nodo*)malloc(sizeof(struct nodo));
inizio->num = e->num;
inizio->next = NULL;
fine = inizio;
}
else{
fine->next = (struct nodo*)malloc(sizeof(struct nodo));
fine = fine->next;
fine->num = e->num;
fine->next = NULL;
}
}
e = e->next;
}
}
int min = -1;
for(i=0; i<n; i++)
if(tempi[i] != -1)
if(tempi2[i] != -1)
if(tempi[i] <= t){
if(min == -1){
min = t + tempi2[i];
}
else{
if(min > t + tempi2[i])
min = t + tempi2[i];
}
}
return min;
}
( http://pastebin.com/1kRiTdDM )
Il problema è che per il testcase 11 mi da risultato non corretto.
Dimentico qualcosa, qualche situazione particolare?
In pratica il mio algoritmo è:
- costruisco il grafo (in cui i nodi sono orientati secondo l’orientamento iniziale)
- trovo il cammino minimo per tutti i nodi partendo dal nodo 0 (-1 se non posso arrivare al nodo)
- senza girare gli archi, trovo il cammino minimo per tutti i nodi partendo dal nodo n-1 (come prima -1 se non posso arrivare al nodo)
- se posso raggiungere un nodo i sia dal nodo 0 sia dal nodo n-1 e lo raggiungo partendo da 0 prima dell’alta marea allora posso passare dal nodo 0 al nodo n-1 in un tempo pari a t+<tempo dal nodo 0 al nodo i>
- scegliendo il minimo fra questi valori trovo la soluzione (-1 se non esiste)
Ci sei alle OII?