Hướng dẫn giải của Tham quan Thành 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.
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 flashmt
#include <iostream> #include <algorithm> #include <cstdio> #define oo 1000111222 using namespace std; int n,x,d[111][111],visited[111]; long long ans; int main() { cin >> n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { scanf("%d",&d[i][j]); if (!d[i][j]) d[i][j]=oo; } for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); visited[x=1]=1; while (1) { int y=0,best=oo-1; for (int i=2;i<n;i++) if (!visited[i] && d[x][i]<best) best=d[x][i], y=i; if (!y) break; ans+=d[x][y]; visited[x=y]=1; } ans+=d[x][n]; cout << ans << endl; }
Code mẫu của happyboy99x
#include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; const int N = 111; typedef pair<int, int> ii; priority_queue<ii, vector<ii>, greater<ii> > a[N]; int n, c[N][N], vst[N]; void enter() { scanf("%d", &n); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d",&c[i][j]), c[i][j] = c[i][j] == 0 ? 1000000000 : c[i][j]; } void floyd() { for(int k = 1; k <= n; ++k) for(int u = 1; u <= n; ++u) for(int v = 1; v <= n; ++v) c[u][v] = min(c[u][k] + c[k][v], c[u][v]); } void solve() { for(int u = 1; u <= n; ++u) for(int v = 1; v < n; ++v) a[u].push(ii(c[u][v], v)); int res = 0, u = 1; while(true) { vst[u] = 1; while(!a[u].empty() && vst[a[u].top().second]) a[u].pop(); if(a[u].empty()) { res += c[u][n]; break; } else { int v = a[u].top().second; res += a[u].top().first; a[u].pop(); u = v; } } printf("%d\n", res); } int main() { enter(); floyd(); solve(); return 0; }
Code mẫu của ladpro98
program TTRIP; uses math; const maxn=101; fi=''; oo=trunc(1e9); var a:array[1..maxn,1..maxn] of longint; chk:array[1..maxn] of boolean; n:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi);reset(inp); readln(inp,n); for i:=1 to n do for j:=1 to n do begin read(inp,a[i,j]); if a[i,j]=0 then a[i,j]:=oo; 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 a[i,j]:=min(a[i,j],a[i,k]+a[k,j]); end; procedure process; var res,s,i,j,m,minw:longint; begin s:=1;res:=0; for i:=2 to n-1 do begin minw:=oo;m:=0; for j:=2 to n-1 do if (not chk[j]) and (a[s,j]<minw) then begin m:=j; minw:=a[s,j]; end; if minw=oo then break; inc(res,minw); chk[m]:=true; s:=m; end; write(res+a[s,n]); end; begin input; floyd; process; end.
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); int n, c[111][111], visited[111]; int main() { scanf("%d", &n); FOR(i,1,n) FOR(j,1,n) { scanf("%d", &c[i][j]); if (i != j && c[i][j] == 0) c[i][j] = 1000111000; } FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) c[i][j] = min(c[i][j], c[i][k] + c[k][j]); int pos = 1, res = 0; visited[1] = true; while (pos != n) { int best = -1; FOR(next,2,n-1) if (!visited[next]) if (best == -1 || c[pos][next] < c[pos][best] || (c[pos][next] == c[pos][best] && next < best)) { best = next; } if (best == -1) best = n; res += c[pos][best]; pos = best; visited[best] = true; } cout << res << endl; return 0; }
Code mẫu của hieult
#pragma comment(linker, "/STACK:16777216") #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.000001 #define maxn 2002 #define base 1000000000 #define modunlo 111539786 #define oo 1000000002 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define ull unsigned long long double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long int64; int n, a[105][105], flag[105] = {0}, u = 1, v , kq = 0, MIN; int main(){ //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); scanf("%d",&n); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ scanf("%d",&a[i][j]); if(!a[i][j]) a[i][j] = oo; } 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]; a[k][j] = a[j][i] + a[i][k]; } } flag[1] = 1; while(true){ v = 0; MIN = oo; for(int i = 1; i < n; i++){ if(a[u][i] < MIN && !flag[i]){ v = i; MIN = a[u][i]; } } if(v == 0){ break; } else{ kq += a[u][v]; u = v; flag[u] = 1; } } kq += a[u][n]; printf("%d",kq); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; int n,a[105][105]; int INF = (1 << 30) - 5; bool check[105]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { scanf("%d", &a[i][j]); if (i != j && !a[i][j]) a[i][j] = INF; } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) a[i][j] = min(a[i][j],a[i][k] + a[k][j]); int ret = 0,start = 0; for (int iter = 0; iter < n - 2; iter++) { int len = INF,pos; for (int j = 1; j < n - 1; j++) if (!check[j] && a[start][j] < len) { len = a[start][j]; pos = j; } ret += len; check[pos] = true; start = pos; } printf("%d\n", ret + a[start][n - 1]); }
Bình luận