This firstly happens in 8th test.

Можно считать,  что мы имеем ориентированный взвешенный граф,  у которого максимальная степень вершины равна трём .

Равна она трём потому,  что нам всегда выгодно ехать как можно дальше,  потому что мы заплатили за всю дистанцию.

То есть из какой-то станции ребра с весами C1,  C2 и C3 проводим в как можно более далёкие станции.

Тогда это получается очень сильно разреженный граф,  так как N<=1e4.

На этом графе запускаем алгоритм Дейкстры для разреженных графов.

Я использовал вариант за O(Nlog2N)  с std :: set.

Для расчёта того,  куда проводить ребра,  я использовал бинарный поиск.  И немного запорол реализацию этого поиска.

Мой поиск возвращал первую станцию, которая находится дальше,  чем разрешено.  И  возвращал  он некорректное значение,  если не было такой станции.

Это послужило причиной WA#6.

Причиной WA#2 послужило то,  что я забыл сделать обновление расстояния до пункта назначения.  Так как ребра идут жадно,  то пункт назначения проезжался и в очередь не попадал,  и расстояние соответственно никогда не обновлялось.

3 6 8 20 30 40
7
1 6
3
7
8
13
15
23
//answer: 80

3 6 8 20 30 40
7
3 6
3
7
8
13
15
23
//answer: 40

3 6 8 20 30 40
7
2 5
3
7
8
13
15
23
//answer: 60

1 2 3 1 1000 1000000000
2
1 2
1
//answer: 1

1 2 3 1 1000 1000000000
2
2 1
1
//answer: 1

My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

Could you please give me the file of test node #11???

Hi, could you post the test 11 data?.. I made my code but it's always crashing on this test.

According to the problem statment 1 ≤ L1 < L2 < L3 ≤ 10 ** 9, 1 ≤ C1 < C2 < C3 ≤ 10 ** 9 but test #10 fails with integers (32-bit) for Li and Ci.

why time limit? n*(n+1)/2 operations:

import java.util.*;
public class RailwayTickets {
    public static long l1,l2,l3,c1,c2,c3,n;
    public static int s,t;
    public static long f(long k) {
        if (k>0 && k<=l1) return c1; else
        if (k>l1 && k<=l2) return c2; else
            if (k>l2 && k<=l3) return c3;
        return Long.MAX_VALUE;
    }
public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        l1=in.nextLong();l2=in.nextLong();l3=in.nextLong();c1=in.nextLong();c2=in.nextLong();c3=in.nextLong();n=in.nextLong();s=in.nextInt();t=in.nextInt();
long[] d = new long[10001], c = new long[10001];
if (s>t) {int yed=s;s=t;t=yed;};
for (int i=2;i<=n;i++) c[i]=in.nextLong();
for (int i=1;i<=n;i++) d[i]=Long.MAX_VALUE;
d[s]=0;

for (int i=s+1;i<=t;i++)
     for (int j=s;j<i;j++)
         if (d[i]>d[j]+f(c[i]-c[j])) d[i]=d[j]+f(c[i]-c[j]);

 System.out.println(d[t]);
 }
}

Edited by author 01.12.2011 15:34

Please help.
my code is here http://paste.ubuntu.com/631092/

I already change start and finish points
but still WA #8……
this is my coad
#include<iostream>
using namespace std;
const int maxn=10005;
long long f[maxn][maxn];
int cost[4];
int d[4];
int a[maxn];
int main()
{
            freopen("in.txt","r",stdin);
            for(int i=1;i<=3;i++)
                        cin>>d[i];
            for(int i=1;i<=3;i++)
                        cin>>cost[i];
            int n;
            cin>>n;
            for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                                    f[i][j]=INT_MAX;
            int s,e;
            cin>>s>>e;
            for(int i=2;i<=n;i++)
            {
                        cin>>a[i];
                        int temp=a[i]-a[i-1];
                        if(temp>d[2]) temp=cost[3];
                        else if(temp>d[1]) temp=cost[2];
                        else temp=cost[1];
                        f[i-1][i]=temp;
            }
            for(int i=1;i<=n;i++)
                        f[i][i]=0;
            for(int p=2;p<=n;p++)
                        for(int i=1;i<=n-p;i++)
                                    for(int j=i+1;j<=i+p;j++)
                                    {
                                                int k=1;
                                                while(1)
                                                {
                                                            if(j-k<=i) break;
                                                            if(a[j]-a[j-k]>d[3])break;
                                                            if(a[j]-a[j-k]>d[2])
                                                                        f[i][j]=min(f[i][j],f[i][j-k]+cost[3]);
                                                            else if(a[j]-a[j-k]>d[1])
                                                                        f[i][j]=min(f[i][j],f[i][j-k]+cost[2]);
                                                            else f[i][j]=min(f[i][j],f[i][j-k]+cost[1]);
                                                            k++;
                                                }
                                                k=1;
                                                while(1)
                                                {
                                                            if(i+k>=j) break;
                                                            if(a[i+k]-a[i]>d[3]) break;
                                                            if(a[i+k]-a[i]>d[2])
                                                                        f[i][j]=min(f[i][j],f[i+k][j]+cost[3]);
                                                            else if(a[i+k]-a[i]>d[1])
                                                                        f[i][j]=min(f[i][j],f[i+k][j]+cost[2]);
                                                            else f[i][j]=min(f[i][j],f[i+k][j]+cost[1]);
                                                            k++;
                                                }
                                    }
            int aaa=min(s,e);
            int bbb=max(e,s);
            cout<<f[aaa][bbb]<<endl;
            return 0;
}

3 100 10000 100 101 102
35
1 34
0
3
3
3
...
3
99
100

i guess the answer is 201(1-35-34)
can DP give this answer? i think only ShortestPath can give this answer.

who is answer it now,i had passed today, simple DP

This is my program:
[code deleted]
Be careful of the s and t.In TEST#8,s>t.

Edited by moderator 23.10.2019 08:45

I have used DP to solve..
but I find 2 man is 0.031.
is there a faster algorithm?

If you have WA on test #3 or on test #1 or on test #2 you must use DP! Else if you have WA on test #4 you must use unsigned int or int 64 or long. If you have WA on test #8 you must change start and finish points ( 6-2 and 2-6 is equal ) !^_^!

Language:C++
Err On:URAL test 8

#include <iostream>
#include <stdio.h>

using namespace std;

struct Point{
       long Dist,Money;
}a[11000];

int main(){
    long L1,L2,L3,C1,C2,C3,n,i,j;
    short Start,End;

    scanf("%ld %ld %ld %ld %ld %ld %ld %ld %ld", &L1, &L2, &L3, &C1, &C2, &C3, &n, &Start, &End);
    a[1].Dist=0;
    for (i=2;i<=n;i++){
        scanf("%ld", &a[i].Dist);
    }
    for (i=Start+1;i<=n;i++){
        a[i].Money=2000000000;
    }
    a[Start].Money=0;
    for (i=Start;i<=End;i++){
        for (j=Start+1;j<=End;j++){
            long Money;
            if (a[j].Dist-a[i].Dist<=L1){
               Money=C1;
            } else if (a[j].Dist-a[i].Dist<=L2){
              Money=C2;
            } else if (a[j].Dist-a[i].Dist<=L3){
              Money=C3;
            } else {
              Money=2000000000;
              break;
            }
            if (a[i].Money+Money<a[j].Money){
               a[j].Money=a[i].Money+Money;
            }
        }
    }

    printf("%ld\n", a[End].Money);
    //return 0;
    cin >> i;
}

I use DP do solve it,like LIS.
Who can give me testdata of test8?please.