CENTRE28 – SPOJ

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

Thuật toán:

  • Tìm đường đi ngắn nhất giữa đỉnh 1 đến mọi đỉnh và giữa đỉnh n đến mọi đỉnh sử dụng thuật toán Dijkstra. Đồng thời ta tính số đường đi ngắn nhất.
  • Gọi d1[i] là đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi d2[i] là đường đi ngắn nhất từ đỉnh n đến i
  • Gọi f1[i] là số đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi f2[i] là số đường đi ngắn nhất từ đỉnh n đến i
  • Điều kiện để đỉnh i có thể làm trung tâm kinh tế thứ 3 là: (d1[i]+dn[i]<>d1[n]) hoặc (f1[i]*fn[i]<>f1[n])

Code:

Pascal

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     u,v,w:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        {for i:=1 to n do writeln(d1[i]);}
        writeln(res);
        for i:=1 to res do writeln(ans[i]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int n, m;
struct data{
    int u, w;
    bool operator <(const data &op) const
    {
        return w > op.w;
    }
};
vector< data > adj[MAXN];
priority_queue<data, vector<data> > q;
int d[3][MAXN];
long long f[3][MAXN];
void min_path(int cs, int s)
{
    FORE(u, 1, n) d[cs][u] = INF;
    d[cs][s] = 0; f[cs][s] = 1;
    q.push((data){s, 0});
    while (q.size()){
        int u = q.top().u;
        int cost_to_u = q.top().w;
        q.pop();
        if (cost_to_u != d[cs][u]) continue;
        FOR(i, 0, adj[u].size()){
            int v = adj[u][i].u;
            int w = adj[u][i].w;
            if (d[cs][v] > d[cs][u] + w){
                d[cs][v] = d[cs][u] + w;
                f[cs][v] = f[cs][u];
                q.push((data){v, d[cs][v]});
            }
            else
            if (d[cs][v] == d[cs][u] + w) f[cs][v] += f[cs][u];
        }
    }
}
vector< int > ans;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("CENTRE.inp", "r", stdin);
    freopen("CENTRE.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> n >> m;
    int u, v, w;
    FORE(i, 1, m){
        cin >> u >> v >> w;
        adj[u].push_back((data){v, w});
        adj[v].push_back((data){u, w});
    }
    min_path(1, 1);
    min_path(2, n);
    FORE(u, 1, n) if (d[1][u] + d[2][u] > d[1][n] || (d[1][u] + d[2][u] == d[1][n] && 1ll * f[1][u] * f[2][u] < f[1][n])) ans.push_back(u);
    cout << ans.size() << endl;
    FOR(i, 0, ans.size()) cout << ans[i]<<endl;
    return 0;
}

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();
}

DHFRBUS – SPOJ

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

Thuật toán:

  • Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
  • Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
  • Kết quả là d[t,k].

Code:

{$inline on}
 
const   fi      ='';
        fo      ='';
        maxN    =trunc(1e5)*2;
        maxM    =trunc(1e5)*10;
        maxK    =5;
        oo       =2*trunc(1e12);
type    Tadj    =record
                v,w,link:int64;
        end;
 
        THeap   =record
                v1,v2:int64;
        end;
 
        Arr1    =array[0..maxN] of int64;
        Arr2    =array[0..maxM] of Tadj;
        Arr4    =array[0..maxN*maxK] of THeap;
        Arr5    =array[0..maxN,0..maxK] of int64;
 
var     n, m, k :longint;
        Adj     :arr2;
        Head    :arr1;
        s, t    :longint;
        d       :arr5;
        Pos     :arr5;
        H       :arr4;
        nHeap   :longint;
        c       :longint;
//heapmin;
procedure hv(var a, b:int64);
var     tg      :int64;
begin
        tg:=a;a:=b;b:=tg;
end;
 
procedure UpHeap(i:longint);
begin
 
        if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit;
        hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]);
        hv(H[i div 2].v1,H[i].v1);
        hv(H[i div 2].v2,H[i].v2);
        UpHeap(i div 2);
end;
 
procedure DownHeap(i:longint);
var     j :longint;
begin
        j:=i*2;
        if j>nHeap then exit;
        if (j<nheap) and (d[H[j+1].v1,H[j+1].v2]<d[H[j].v1,H[j].v2]) then inc(j);
        if d[H[i].v1,H[i].v2]<=d[H[j].v1,H[j].v2] then exit;
        hv(Pos[H[i].v1,H[i].v2],Pos[H[j].v1,H[j].v2]);
        hv(H[i].v1,H[j].v1);
        hv(H[i].v2,H[j].v2);
        DownHeap(j);
end;
 
procedure Update(u,x:longint);
var     p :longint;
begin
        p:=pos[u,x];
        if p=0 then
                begin
                        inc(nHeap);
                        H[nheap].v1:=u;
                        H[nheap].v2:=x;
                        Pos[u,x]:=nHeap;
                        p:=nHeap;
                end;
        UpHeap(p);
end;
 
procedure GetMin(var u, x:longint);
begin
        if nheap=0 then
                begin
                        u:=0;x:=0;
                        exit;
                end;
        u:=H[1].v1;x:=H[1].v2;
        H[1].v1:=H[nHeap].v1;
        H[1].v2:=H[nheap].v2;
        Pos[H[1].v1,H[1].v2]:=1;
        dec(nHeap);
        downHeap(1);
end;
 
procedure Dijkstra;
var      i, v, w      :int64;
        ans     :int64;
        u     ,x  :longint;
begin
        fillchar(pos,n,0);
        for u:=1 to n do
                for x:=0 to k do d[u,x]:=oo;
        nHeap:=0;
        d[s,0]:=0;
        Update(s,0);
        repeat
                GetMin(u,x);
                i:=head[u];
                if u=0 then exit;
                while i<>0 do
                begin
                        v:=adj[i].v;
                        w:=adj[i].w;
                        if d[v,x]>d[u,x]+w then
                        begin
                                d[v,x]:=d[u,x]+w;
                                Update(v,x);
                        end;
                        if (x<k) and (d[v,x+1]>d[u,x]) then
                        begin
                                d[v,x+1]:=d[u,x];
                                Update(v,x+1);
                        end;
                        i:=adj[i].link;
                end;
        until nHeap=0;
        ans:=oo;
        ans:=d[t,k];
        {for x:=0 to k do
                if d[t,x]<ans then
                                ans:=d[t,x];}
        writeln(ans);
end;
 
procedure Tadd(u,v,w:longint);
begin
        inc(c);
        Adj[c].v:=v;
        Adj[c].w:=w;
        Adj[c].link:=head[u];
        head[u]:=c;
end;
 
procedure xuly;
var     i, u, v, w      :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n, m, k, s, t);
        c:=0;
        fillchar(head,sizeof(head),0);
        for i:=1 to m do
                begin
                        readln(u,v,w);
                        Tadd(u,v,w);
                        Tadd(v,u,w);
                end;
        Dijkstra;
        close(input);close(output);
end;
 
begin
        xuly;
end.