Editorial for Sa mạc


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define fi first
#define se second
#define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define INF 1000000000
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<LL> vi;

vvii g;
LL n, m, c;

void enter() {
    scanf("%lld%lld%lld",&n,&m,&c);
    g = vvii(n, vii());
    for(LL i = 0; i < m; ++i) {
        LL u, v, l; scanf("%lld%lld%lld",&u,&v,&l);
        g[--u].push_back(ii(--v, l));
        g[v].push_back(ii(u, l));
    }
}

inline LL ceil(int a, int b) {
    return b <= 0 ? INF : a / b + (a % b != 0);
}

void solve() { //Dijkstra's Algorithm
    vi d = vi(n, INF); d[n-1] = 0;
    priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, n-1));
    while(!qu.empty()) {
        LL du = qu.top().fi, u = qu.top().se; qu.pop();
        if (du > d[u]) continue;
        TR(g[u], it) {
            LL v = it->fi, l = it->se;
            if(du + l <= c) {
                if(du + l < d[v]) qu.push(ii(d[v] = du + l, v));
            } else {
                LL k = ceil(du - c + l, c - l - l);
                if(k != INF && (k+k+1)*l + du < d[v]) qu.push(ii(d[v] = (k+k+1)*l + du, v));
            }
        }
    }
    printf("%lld\n", d.front());
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    LL tc; scanf("%lld", &tc);
    while(tc--) {
        enter();
        solve();
    }
    return 0;
}

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung (algorithm by taek)
{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=101;
  oo=1000000000000;
type
  list=^node;
  node=record
         u,c:longint;
         next:list;
       end;
var
  f1,f2:text;
  test,n,gh,hsize:longint;
  ke:array[1..MAXN] of list;
  h,hpos:array[1..MAXN] of longint;
  need:array[1..MAXN] of int64;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure add(u,c:longint; var a:list);
var p:list;
begin
  new(p); p^.u:=u; p^.c:=c;
  p^.next:=a; a:=p;
end;
procedure inp;
var
  m,u,v,c:longint;
begin
  read(f1,n,m,gh);
  fillchar(ke,sizeof(ke),0);
  for m:=1 to m do
    begin
      read(f1,u,v,c);
      add(u,c,ke[v]);
      add(v,c,ke[u]);
    end;
end;
procedure ans;
begin
  if need[1]=oo then writeln(f2,-1)
  else writeln(f2,need[1]);
end;
//Xu ly heap
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (need[h[j+1]]<need[h[j]]) then inc(j);
      if (need[h[j]]<need[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (need[h[i]]<need[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]); hpos[h[1]]:=1;
  dec(hsize); downHeap(1);
end;
procedure solve;
var
  u,v:longint;
  x,one,c:int64;
  p:list;
begin
  for u:=1 to n-1 do need[u]:=oo; need[n]:=0;
  hsize:=0; fillchar(hpos,sizeof(hpos),0); push(n);
  while hsize>0 do
    begin
      pop(u);
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; c:=p^.c; p:=p^.next;
          //Khong the qua canh (u,v)
          if c>gh then continue;
          //Chi can luong <=gh-c de den dich (chi can qua canh (u,v) 1 lan)
          if need[u]<=gh-c then x:=need[u]+c
          else if gh-c<<1<=0 then continue
          else
            begin
              //Luong nuoc chuyen duoc trong 1 lan
              one:=(need[u]-(gh-c)-1) div (gh-c<<1)+1;
              //Luong nuoc can
              x:=need[u]+(one<<1+1)*c;
            end;
          if x<need[v] then
            begin
              need[v]:=x;
              if hpos[v]=0 then push(v)
              else upHeap(hpos[v]);
            end;
        end;
    end;
end;
begin
  openF;
  read(f1,test);
  for test:=1 to test do
    begin
      inp;
      solve;
      ans;
    end;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>


long long min(long long a,long long b)
{
    if(a<b) return a;
    else return b;
}
int main()
{
    long long A = 1000000000, B = 1000000;
    long long oo = A*B;
    //freopen("NK05DSRT.in","r",stdin);
    int test,flag[101],n,m,c,x,y,l;
    long long a[101][101],d[101];
    scanf("%d",&test);
    for(int ii = 1;ii<=test;ii++)
    {
        scanf("%d %d %d",&n,&m,&c);
        for(int i = 1;i<=n;i++)
        {
            d[i] = oo;
            flag[i] = 0;
            for(int j = 1;j<=n;j++)
                a[i][j] = oo;
        }
        for(int i = 1;i<=m;i++)
        {
            scanf("%d %d %d",&x,&y,&l);
            if(a[x][y]>l)
            {
            a[x][y] = l;
            a[y][x] = l;
            }
        }
        int u = n;flag[n] = 1;d[n]=0;
        while(u!=1)
        {
            for(int i = 1;i<=n;i++)
                if(flag[i]==0 && a[i][u] < oo)
                {
                     long long k = oo;
                     if(a[i][u]>c);
                     else if(d[u]+a[i][u]<=c)
                         k = d[u]+a[i][u]; 
                     else if(c>2*a[i][u])
                     {
                          long long t = (d[u]-c+a[i][u]-1)/(c-2*a[i][u])+1;
                          k = t*c+d[u]-t*(c-2*a[i][u])+a[i][u];
                     }
                     d[i] = min(k,d[i]);
                }
           long long f = 0,minn = oo;
           for(int i = 1;i<=n;i++)
                if(flag[i]==0 && d[i]<minn)
                {
                     f = i;
                     minn = d[i];
                }
           u = f;
           flag[f] = 1;
           //for(int i = 1;i<=n;i++)
           //printf("%d ",d[i]);
           //printf(" ___%d____",u);
           //printf("\n");
        } 
        printf("%lld\n",d[1]);                       
    }
    //getch();
}

Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;

int N, C;
int a[111][111];
long long d[111];

void process() {
    memset( d, 0x3f, sizeof(d));
    d[N] = 0;
    queue<int> q;
    q.push(N);
    while(!q.empty()) {
        int u = q.front(), v;
        long long L, tmp, k, xx;
        q.pop();
        for(v=1;v<=N;++v) if((L=a[u][v])>0 && a[u][v]<=C){
            // 1 lan
            if(C-L>=d[u]) {
                tmp = d[u] + L;
                if(d[v]>tmp) {
                    d[v] = tmp;
                    q.push(v);
                }
            }
            // nhieu lan
            else if(C>2*L) {
                xx = (d[u]+L-C) / (C-2*L) - 1;
                xx >?= 1;
                for(k=xx;k<=xx+10;++k) {
                    tmp = d[u] + L - k * (C - 2*L);
                    if(tmp>=L && tmp<=C) {
                        tmp = tmp + k * C;
                        if(d[v]>tmp) {
                            d[v] = tmp;
                            q.push(v);
                        }
                    }
                }
            }
        }
    }
    printf("%lld\n",d[1]);
}

int main() {
    int st, M, u, v, l;
    scanf("%d",&st);
    while(st--) {
        scanf("%d%d%d",&N,&M,&C);
        memset( a, 0, sizeof(a));
        for(int i=0;i<M;++i) {
            scanf("%d%d%d",&u,&v,&l);
            a[u][v] = a[v][u] = l;
        }
        process();
    }
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.