Hướng dẫn giải của Sa mạc


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.