Oppgavebeskrivelse
Kongeriket JOI er et kongerike som består av $N$ byer, nummerert fra $1$ til $N$. I Kongeriket JOI er det $M$ enveiskjørte motorveier som forbinder disse byene, nummerert fra $1$ til $M$. Ved å følge motorvei $i$ ($1 \le i \le M$) kan man reise fra by $A_i$ til by $B_i$, og tiden det tar å kjøre gjennom den er $L_i$.
Hver gang man kjører på en motorvei, påløper det bompenger. Bompengene for motorvei $i$ er på sitt billigste $C_i$, men fordi alle arbeidere i Kongeriket JOI misliker overtidsarbeid, blir bompengene høyere jo lenger unna tiden er fra et referansetidspunkt $0$. Mer spesifikt, hvis man reiser fra by $A_i$ ved tidspunkt $t$ og kjører motorvei $i$, uttrykkes bompengene ved hjelp av en konstant $K$ som $C_i + K \times |t|$, der $|t|$ betegner absoluttverdien av $t$.
Du som bor i by $1$, planlegger en tur til by $N$, der vennen din bor. Siden du ønsker å reise fra by $1$ til by $N$ ved hjelp av motorveier, vil du først sjekke om det er mulig, og hvis det er mulig, vil du også finne ut hva den minste mulige totale bompengesummen er. Her kan du fritt velge reiserute og tidspunkt for avreise fra hver by. Spesielt kan du reise fra by $1$ ved et negativt tidspunkt, eller bruke tid på å oppholde deg i en by uten å kjøre på noen motorvei.
Gitt informasjonen om motorveiene og konstanten $K$, skriv et program som avgjør om det er mulig å reise fra by $1$ til by $N$ ved hjelp av motorveier, og hvis det er mulig, finner den minste totale bompengesummen.
Under begrensningene i denne oppgaven kan det bevises at dersom det er mulig å reise fra by $1$ til by $N$ ved hjelp av motorveier, vil den minste totale bompengesummen alltid være et heltall.
Begrensninger
- $2 \le N \le 4\,000$.
- $1 \le M \le 8\,000$.
- $0 \le K \le 100\,000$.
- $1 \le A_i \le N$ ($1 \le i \le M$).
- $1 \le B_i \le N$ ($1 \le i \le M$).
- $A_i \neq B_i$ ($1 \le i \le M$).
- $1 \le L_i \le 1\,000\,000$ ($1 \le i \le M$).
- $0 \le C_i \le 10^9$ ($1 \le i \le M$).
- Alle inndataverdier er heltall.
Deloppgaver
- ($9$ poeng) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ poeng) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ poeng) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ poeng) $N \le 100$, $M \le 200$, og følgende begrensning gjelder:
- $N$ er et partall, og $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), der $\lfloor x \rfloor$ betegner det største heltallet som er mindre enn eller lik $x$.
- ($16$ poeng) $N \le 100$, $M \le 200$.
- ($11$ poeng) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ poeng) Ingen ytterligere begrensninger.
Inndata
Inndata gis i følgende format:
N M K A_1 B_1 L_1 C_1 A_2 B_2 L_2 C_2 : A_M B_M L_M C_M
Utdata
Hvis det er umulig å reise fra by $1$ til by $N$ ved hjelp av motorveier, skriv ut -1. Hvis det er mulig, skriv ut på $1$ linje heltallet som representerer den minste totale bompengesummen.
Eksempel 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Byene og veiene i Kongeriket JOI er illustrert nedenfor. Sirkler representerer byer, piler representerer veier, og ved siden av hver vei står verdiene av $L_i$ og $C_i$ for den veien i denne rekkefølgen. Tallet som er skrevet inne i hver sirkel representerer nummeret på den byen.
Ved å reise på følgende måte blir den totale bompengesummen $15$:
- Tidspunkt $-1$: Reis fra by $1$ og kjør mot by $3$. Det koster $10 + 2 \times |-1| = 12$ i bompenger.
- Tidspunkt $0$: Ankom by $3$ og kjør umiddelbart mot by $4$. Det koster $3 + 2 \times |0| = 3$ i bompenger.
- Tidspunkt $5$: Ankom by $4$.
Siden det ikke finnes noen måte å reise på med en total bompengesum mindre enn $15$, skriver vi ut $15$.
Dette eksempelinndataet tilfredsstiller begrensningene i deloppgave $2, 5, 6, 7$.
Eksempel 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Bare verdien av $K$ er forskjellig fra Eksempel $1$.
Ved å reise på følgende måte blir den totale bompengesummen $9$:
- Tidspunkt $-3$: Reis fra by $1$ og kjør mot by $2$. Det koster $2 + 0 \times |-3| = 2$ i bompenger.
- Tidspunkt $0$: Ankom by $2$ og kjør umiddelbart mot by $3$. Det koster $4 + 0 \times |0| = 4$ i bompenger.
- Tidspunkt $1$: Ankom by $3$ og bli værende i by $3$.
- Tidspunkt $3$: Reis fra by $3$ og kjør mot by $4$. Det koster $3 + 0 \times |3| = 3$ i bompenger.
- Tidspunkt $8$: Ankom by $4$.
Siden det ikke finnes noen måte å reise på med en total bompengesum mindre enn $9$, skriver vi ut $9$.
Dette eksempelinndataet tilfredsstiller begrensningene i deloppgave $1, 2, 5, 6, 7$.
Eksempel 3
2 1 10 2 1 4 7
-1
Siden det er umulig å reise fra by $1$ til by $2$ ved hjelp av motorveier, skriver vi ut -1.
Dette eksempelinndataet tilfredsstiller begrensningene i deloppgave $2, 5, 6, 7$.
Eksempel 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Dette eksempelinndataet tilfredsstiller begrensningene i deloppgave $2, 3, 5, 6, 7$.
Eksempel 5
8 8 2 1 2 1 5 5 6 3 1 2 4 10 18 3 5 3 1 1 3 4 2 5 6 2 2 2 5 2 3 6 8 1 1
25
Det kan finnes flere veier som har det samme paret $(A_i, B_i)$.
Dette eksempelinndataet tilfredsstiller begrensningene i deloppgave $2, 4, 5, 6, 7$.
Eksempel 6
6 10 100000 4 2 212037 752027141 2 5 667097 1571491 2 1 769275 576006950 1 2 711969 526189398 5 3 733555 206320177 3 4 364807 802102091 1 4 467240 183184247 3 5 44994 15991843 5 3 613192 782356546 4 6 832593 639529758
47546714005
Dette eksempelinndataet tilfredsstiller begrensningene i deloppgave $5, 6, 7$.