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 <iostream>
#include <cmath>
#include <fstream>
#include <bits/stdc++.h>
#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 ((l<qn) && (kc[q[l+1]]<kc[q[l]])) l++;
        if (kc[q[l]]>=kc[v]) break;
        q[k]=q[l];
        vt[q[k]]=k;
        k=l;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int initq() {qn=0; vt[0]=0; kc[0]=-1;}
int put(int u) {q[++qn]=u; vt[u]=qn; up(qn);}
int get() {int kq=q[1]; q[1]=q[qn--]; vt[q[1]]=1; down(1); return kq;}
int update(int u) {int k=vt[u]; up(k);}
int qempty() {return (qn==0);}
 
// Ham dijstra tim khoang cach ngan nhat
int dijstra()
{
    initq();
    kc[1]=0; prev[1]=-(n+1);
    put(1);
    while (!qempty())
    {
        int u=get(); prev[u]=-prev[u];
        tt[++sl]=u;
        for (long i=tro[u]; i<tro[u+1]; i++)
        {
            int v;
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            if ((prev[v]<0) && (kc[v]>kc[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<tro[u+1]; i++)
        {
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            tg=t[ke[i]]; cp=c[ke[i]];
            if ((kc[v]==kc[u]+tg) && (nl[u]>=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<tro[2]; i++)
    {
        int v;
        if (dau[ke[i]]!=1) v=dau[ke[i]]; else v=cuoi[ke[i]];
        if (v==n) out << t[ke[i]] << ' ' << c[ke[i]] << '\n';
    } */
    }
 
// CHUONG TRINH CHINH
int main()
{
    doc();
    dungdt();
    dijstra();
    solve();
    viet();
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*