Editorial for Nguy hiểm rõ ràng trước mắt


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 flashmt

const maxn=100;
      max=100000000;
var a:array[1..maxn,1..maxn] of longint;
    b:array[1..10000] of byte;
    n:byte;
    m:integer;

procedure rf;
var i,j:byte; k:integer;
begin
     readln(n,m);
     for k:=1 to m do readln(b[k]);
     for i:=1 to n do
     begin
          for j:=1 to n do
              read(a[i,j]);
          readln;
     end;
end;

procedure pr;
var i,j,k:byte;
begin
     for i:=1 to n do
         for j:=1 to n do
             for k:=1 to n do
                 if a[j,k]>a[j,i]+a[i,k] then
                    a[j,k]:=a[j,i]+a[i,k];
end;

procedure wf;
var i:integer; re:longint;
begin
     re:=0;
     for i:=1 to m-1 do
         re:=re+a[b[i],b[i+1]];
     write(re);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 105
#define M 10005

int a[M], g[N][N], n, m;

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    scanf( "%d%d", &n, &m );
    rep(i,m) { scanf( "%d", a+i ); --a[i]; }
    rep(i,n) { rep(j,n) scanf( "%d", &g[i][j] ); g[i][i] = INF; }
    rep(k,n) rep(i,n) rep(j,n) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    long long res = 0; rep(i,m-1) res += g[a[i]][a[i+1]];
    cout << res << endl;
    return 0;
}

Code mẫu của ladpro98

program vdanger;
uses    math;
const   maxn=101;
        fi='';
var     a:array[1..maxn,1..maxn] of longint;
        path:array[1..maxn*maxn] of longint;
        n,m:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,m);
        for i:=1 to m do readln(inp,path[i]);
        for i:=1 to n do
        begin
                for j:=1 to n do read(inp,a[i,j]);
                readln(inp);
        end;
        close(inp);
end;

procedure Floyd;
var     i,j,k:longint;
begin
        for k:=1 to n do
        for i:=1 to n do
        for j:=1 to n do
        if i<>j then
        a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
end;

procedure output;
var     res,i:longint;
begin
        res:=0;
        for i:=1 to m-1 do
        inc(res,a[path[i],path[i+1]]);
        write(res);
end;

begin
        input;
        Floyd;
        output;
end.

Code mẫu của RR

uses math;
var
  i,j,k,n,m,res:longint;
  a:array[1..10111] of longint;
  c:array[1..111,1..111] of longint;
begin
  read(n,m);
  for i:=1 to m do read(a[i]);
  for i:=1 to n do
  for j:=1 to n do
    read(c[i,j]);

  for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
      c[i,j]:=min(c[i,j],c[i,k]+c[k,j]);

  res:=c[1,a[1]]+c[a[m],n];
  for i:=2 to m do
    inc(res,c[a[i-1],a[i]]);
  writeln(res);
end.

Code mẫu của hieult

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

int main()
{
    //freopen("VDANGER.in","r",stdin);
    long long n,m,t[10001],a[101][101];
    scanf("%lld %lld",&n,&m);
    for(int i = 1;i<=m;i++)
        scanf("%lld",&t[i]);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            scanf("%lld",&a[i][j]);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            for(int k = 1;k<=n;k++)
                if(a[j][i]+a[i][k]<a[j][k])
                {
                    a[j][k] = a[j][i]+a[i][k];
                }
    long long KQ = 0;
    for(int i = 1;i<m;i++)
       KQ = KQ+a[t[i]][t[i+1]];
    printf("%lld",KQ);
   // getch();
}

Code mẫu của ll931110

Program VDANGER;
        Const
                input  = '';
                output = '';
        Var
                  a: array[1..10000] of longint;
                n,m: longint;
                  c: array[1..100,1..100] of longint;

Procedure init;
          Var
                  f: text;
                i,j: longint;
          Begin
                Assign(f, input);
                        Reset(f);

                Readln(f, n, m);
                For i:= 1 to m do readln(f, a[i]);

                For i:= 1 to n do
                        Begin
                                For j:= 1 to n do read(f, c[i,j]);
                                Readln(f);
                        End;

                Close(f);
          End;

Procedure Floyd;
          Var
                k,u,v: longint;
          Begin
                For k:= 1 to n do
                    For u:= 1 to n do
                        For v:= 1 to n do
                            if c[u,v] > c[u,k] + c[k,v] then
                                      c[u,v]:= c[u,k] + c[k,v];
          End;

Procedure solve;
          Var
                    f: text;
                sum,i: longint;
          Begin
                Assign(f, output);
                        Rewrite(f);

                        sum:= 0;
                        For i:= 1 to m - 1 do
                                sum:= sum + c[a[i],a[i + 1]];

                        Writeln(f, sum);
                Close(f);
          End;

Begin
        init;
        Floyd;
        solve;
End.

Code mẫu của khuc_tuan

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
        // Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(kb.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] ds = new int[m];
        for (int i = 0; i < m; ++i)
            ds[i] = Integer.parseInt(kb.readLine()) - 1;
        int[][] a = new int[n][n];
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(kb.readLine());
            for (int j = 0; j < n; ++j)
                a[i][j] = Integer.parseInt(st.nextToken());
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
        int s = 0;
        long total = 0;
        for (int i = 0; i < ds.length; ++i) {
            total += a[s][ds[i]];
            s = ds[i];
        }
        total += a[s][n - 1];
        System.out.println(total);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.