30/09/2018, 22:53

NK05DSRT - Sa mạc (Cần giúp đỡ)

Chào mọi người,
Mình loay hoay bài này hơn tuần rồi mà không có kết quả.
Chi tiết tại đây: http://vn.spoj.com/status/NK05DSRT/

Còn đây là đề bài: http://vn.spoj.com/problems/NK05DSRT/
Và đây là ý tưởng của mình:

Sử dụng Dijkstra ngược từ đỉnh N về đỉnh 1.

#include <bits/stdc++.h>
using namespace std;

int main()
{
#ifdef gsdt
    freopen("input.txt","r",stdin);
#endif // gsdt

    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,c,m;
        int a[220][220];
        int l[220][220];
        memset(a,0,sizeof(a));
        memset(l,0,sizeof(l));
        scanf("%d%d%d",&n,&m,&c);
        assert(0<n && n<=200);
        assert(0<c && c<=200);
        assert(0<m && m<=200);
        for(int i=1; i<=m; i++)
        {
            int x,y,w;
            scanf("%d%d%d",&x,&y,&w);
            if(w>c) continue;
            a[x][++a[x][0]]=y;
            a[y][++a[y][0]]=x;
            l[x][y]=w;
            l[y][x]=w;
        }

        int64_t dp[220];
        bool fr[220];
        memset(fr,true,sizeof(fr));
        for(int i=0; i<220; i++) dp[i]=LLONG_MAX    ;
        dp[n]=0;

        while(true)
        {
            int64_t u=0,MIN=LLONG_MAX    ;
            for(int i=1; i<=n; i++)
                if(dp[i]<MIN && fr[i])
                    MIN=dp[i],
                    u=i;
            if(u==1) break;
            fr[u]=false;

            for(int i=1; i<=a[u][0]; i++)
            {
                int64_t v=a[u][i];
                if(!fr[v])continue;

                int64_t need=dp[u];
                int64_t L=l[u][v];
                int64_t water;
                for(int j=0; j<=1000; j++)
                {
                    if(j!=0 && c-2*L<=0) break;
                    int y=need-j*(c-2*L);
                    if(y<0)break;
                    if(y+L<=c)
                    {
                        water=c*j+y+L;
                        assert(0<water && water<LLONG_MAX);
                        dp[v]=min(dp[v],water);
                        //break;
                    }
                }
                
            }
        }
        if(dp[1]==LLONG_MAX    ) printf("NO
");
        cout<<dp[1]<<endl;
    }
}

Rất mong các cao thủ vào giúp đỡ.
@david15894 @Gio

Tao Không Ngu. viết 00:54 ngày 01/10/2018

This post was flagged by the community and is temporarily hidden.

hacked viết 00:55 ngày 01/10/2018

Chú nói có vẻ vui tai? Thế chú đã AC bài này chưa?

‏ viết 01:09 ngày 01/10/2018

hehe vừa được accepted rồi

cái này đúng là Dijkstra ngược từ N về 1 nhưng cách tính độ dài phải có công thức riêng. Gọi cách tính điểm đó là int getNeededAmount(int A, int L, int C) thì quy luật là:
nếu A+L <= C, trả về A+L
nếu C <= 2L, trả về invalid amount
còn lại, tính t = ceil(A+L-C / C-2L), rồi trả về (2t+1)L + A

cách giải thích là ta thấy để có lượng nước A từ ốc đảo 1 tới ốc đảo 2, độ dài 1-2 là L, lượng nước tối đa mang được là C thì các trường hợp dễ thấy là nếu A+L <= C thì ko cần đi vòng (số lần đi vòng là t) mà mang thẳng lượng nước A+L từ ốc đảo 1 qua ốc đảo 2 luôn. Còn nếu ko thì phải đi vòng. Một lần đi vòng tốn 2L nước. Nếu C <= 2L thì mỗi lần đi chả tích cóp được tí nước nào nên trả về invalid amount, và sẽ coi như là ko có đường đi giữa 2 ốc đảo này. Nếu C > 2L thì ví dụ A=16, L=11, C=24, viết giấy ra ta thấy:

24 24 23 
22 22 11
 2  2 12

phải đi 2 vòng. Số lượng nước cần có ở ốc đảo 1 là 24+24+23=71, hay cũng chính là 16+22+22+11. Nếu biết số lần đi vòng ít nhất (t) thì lượng nước trả về là A + (2t+1)L

bây giờ đi tìm t. Lượng nước tích cóp được sau t vòng là t(C - 2L), vì mỗi vòng đi tích cóp được C-2L lít. Vì A+L > C, nên lượng nước cần tích cóp phải >= A+L-C, tốt nhất là bằng, nhưng nếu lớn hơn cũng ko sao, nếu ít hơn thì ko được. Vậy ta có công thức
t(C-2L) >= A+L-C
t >= (A+L-C) / (C-2L)
để t min thì t chính là ceil của (A+L-C) / (C-2L). Ví dụ A=16, L=11, C=24, A+L-C = 3, C-2L = 2, 3/2 = 1.5, ceil(1.5) = 2. Số lần đi vòng là 2. Số lượng nước cần có ở ốc đảo 1 là (2*2+1)*11 + 16 = 55+16 = 71.

có công thức rồi ráp vô thôi

int ceil(int a, int b) //return ceil(a/b)
{
    return a/b + (a%b != 0);
}

int getNeededAmount(int A, int L, int C)
{
    if (A+L <= C) return A+L;
    if (C <= 2*L) return INVALID_AMOUNT;
    int t = ceil(A+L-C, C-2*L);
    return (2*t+1)*L + A;
}

để tránh chia số thực thì viết hàm ceil cho chia 2 số nguyên, cũng dễ

nộp 3 lần, lần 1 lỗi do nộp C++ thường, lần 2 nộp C++14 lỗi do quy luật sai: A+L phải bé hơn hoặc bằng C, lần 3 thì ac

hacked viết 01:04 ngày 01/10/2018