QBROBOT – SPOJ

Đề bài: http://vn.spoj.com/problems/QBROBOT/

Thuật toán:

• Tìm đường đi ngắn nhất bằng Dijkstra
• Chắt nhị phân giá trị w
• Với mỗi giá trị w kiểm tra xem có thỏa mãn không

Code:

#include 
#include 
#include 
#include 
#define MAXN 502
#define MAXM 30002
#define VC 2000000000
int n, m, dau[MAXM], cuoi[MAXM], t[MAXM], c[MAXM], x[MAXN];
long tro[MAXN];
int ke[2*MAXM];
int qn, q[MAXN], vt[MAXN];
long kc[MAXN], nl[MAXN], ds;
int prev[MAXN];
int tt[MAXN], sl=0;
using namespace std;
int doc()
{
    int i;
    cin >> n;
    for (i=1; i<=n; i++) cin >> x[i];
    cin >> m;
    for (i=1; i<=m; i++) cin >> dau[i] >> cuoi[i] >> t[i] >> c[i];
}

// Ham dung do thi
int dungdt()
{
    long u,v;
    int i;
    for (i=1; i<=m; i++) {tro[dau[i]]++; tro[cuoi[i]]++;}
    for (v=0,i=1; i<=n; i++) {u=tro[i]; tro[i]=v+1; v+=u;}
    tro[n+1]=v+1;
    for (i=1; i<=m; i++) {ke[tro[dau[i]]++]=i; ke[tro[cuoi[i]]++]=i;}
    for (i=n; i>=2; i--) tro[i]=tro[i-1]; tro[1]=1;
}

// Cac ham quan ly hang doi uu tien
int up(int k)
{
    int v=q[k];
    while (kc[q[k/2]]>kc[v])
    {
        q[k]=q[k/2];
        vt[q[k]]=k;
        k/=2;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int down(int k)
{
    int v=q[k];
    while (2*k<=qn)
    {
        int l=2*k;
        if ((lkc[u]+t[ke[i]]))
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                update(v);
            }
            if (prev[v]==0)
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                put(v);
            }
        }
    }
    return 0;
}


// Ham kiem tra co di duoc hay khong
int diduoc(long w)
{
    long i,k,u,v,tg,cp,cl;
    for (i=1; i<=n; i++) nl[i]=-VC;
    nl[1]=w;
    for (k=1; k<=sl; k++)
    {
        u=tt[k];
        if (nl[u]>=0)
        for (i=tro[u]; i=cp))
            {
                cl=(x[v]==1) ? w : nl[u]-cp;
                if (cl>nl[v]) nl[v]=cl;
            }
        }
    }
    return (nl[n]>=0);
}

// Ham tim chi phi be nhat (dua vao theo tim kiem nhi phan)
int solve()
{
    long first=0, last=1, lim;
    while (!diduoc(last)) {first=last; last*=2;}
    while (last-first>1)
    {
        lim=(last+first)/2;
        if (diduoc(lim)) last=lim; else first=lim;
    }
    ds=last;
}

// Ham in ket qua
int viet()
{
    cout << ds;
    //<< // '\n';
    /*out << kc[n] << '\n';
    for (long i=tro[1]; i