Editorial for Đến trường
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.
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 fi=''; fo=''; maxn=5005; maxc=2000000000; var n,m:longint; a,w:array[1..40000] of integer; d,s,cur,pos:array[1..maxn] of longint; sl:array[1..maxn] of qword; free:array[1..maxn] of boolean; b:array[1..20000,0..3] of longint; procedure rf; var i,j,x,y,z,t:longint; begin read(n,m); for i:=1 to m do begin for j:=0 to 3 do read(b[i,j]); inc(s[b[i,1]]); if b[i,0]=2 then inc(s[b[i,2]]); end; pos[1]:=1; cur[1]:=1; for i:=2 to n+1 do begin pos[i]:=pos[i-1]+s[i-1]; cur[i]:=pos[i]; end; for i:=1 to m do begin a[cur[b[i,1]]]:=b[i,2]; w[cur[b[i,1]]]:=b[i,3]; inc(cur[b[i,1]]); if b[i,0]=2 then begin a[cur[b[i,2]]]:=b[i,1]; w[cur[b[i,2]]]:=b[i,3]; inc(cur[b[i,2]]); end; end; end; procedure pr; var i,x,t,min:longint; begin for i:=1 to n do begin free[i]:=true; d[i]:=maxc; end; d[1]:=0; free[1]:=false; x:=1; sl[1]:=1; repeat for i:=pos[x] to pos[x+1]-1 do if free[a[i]] then begin if d[a[i]]=d[x]+w[i] then sl[a[i]]:=sl[a[i]]+sl[x] else begin if d[a[i]]>d[x]+w[i] then begin d[a[i]]:=d[x]+w[i]; sl[a[i]]:=sl[x]; end; end; end; min:=maxc-1; t:=0; for i:=1 to n do if free[i] and (d[i]<min) then begin min:=d[i]; t:=i; end; if t=0 then exit; x:=t; free[x]:=false; until not free[n]; end; procedure wf; begin writeln(d[n],' ',sl[n]); end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); rf; pr; wf; close(input); close(output); 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(); i != _e; ++i) #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 30005 typedef long long LL; int d[N], n, m; LL c[N]; vvii g; void dijkstra(vvii&g, int s, int *d, LL *c) { fill(d,d+n,INF); d[s] = 0; c[s] = 1; priority_queue< ii, vii, greater<ii> > qu; qu.push(ii(0,s)); while(!qu.empty()) { int u = qu.top().se, du = qu.top().fi; qu.pop(); if(du > d[u]) continue; tr(g[u],it) { int v = it->fi, l = it->se; if( du + l < d[v] ) { qu.push(ii(d[v] = du+l,v)); c[v] = c[u]; } else if( du + l == d[v] ) c[v] += c[u]; } } } int main() { scanf("%d%d",&n,&m); g.resize(n); rep(i,m) { int k, u, v, l; scanf("%d%d%d%d",&k,&u,&v,&l); g[--u].pb(ii(--v,l)); if(k == 2) g[v].pb(ii(u,l)); } dijkstra(g, 0, d, c); printf("%d %lld\n", d[n-1], c[n-1]); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 5050; const int INF = 1e9; struct Edge { int to, cost; Edge(int to, int cost): to(to), cost(cost) {} }; namespace PriorityQueue { static const int LIMIT = 2e5; vector<int> V[LIMIT]; int size; int cur; void push(int u, int d) { V[d].push_back(u); ++size; } void getMin(int &u, int &du) { while (cur < LIMIT && V[cur].empty()) ++cur; assert(cur < LIMIT); --size; u = V[cur].back(); du = cur; V[cur].pop_back(); } } int d[N]; long long cnt[N];; int n, m; vector<Edge> a[N]; int main() { ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; ++i) { int k, u, v, L; cin >> k >> u >> v >> L; a[u].push_back(Edge(v, L)); if (k == 2) a[v].push_back(Edge(u, L)); } for (int i = 2; i <= n; ++i) d[i] = INF; PriorityQueue::push(1, 0); cnt[1] = 1; while (PriorityQueue::size) { int u, du; PriorityQueue::getMin(u, du); if (d[u] != du) continue; for (auto e : a[u]) { int v = e.to; int c = e.cost; if (d[v] > d[u] + c) { d[v] = d[u] + c; PriorityQueue::push(v, d[v]); cnt[v] = cnt[u]; } else if (d[v] == d[u] + c) { cnt[v] += cnt[u]; } } } cout << d[n] << ' ' << cnt[n] << endl; return 0; }
Code mẫu của RR
{$R-,Q-} const FINP=''; FOUT=''; MAXN=20000; oo=1000000000; type list=^node; node=record u,c:longint; next:list; end; var thuan,nghich:array[1..MAXN] of list; d,hpos,h:array[1..MAXN] of longint; sl:array[1..MAXN] of int64; hsize,n:longint; procedure add(u,c:longint;var a:list); inline; var p:list; begin new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p; end; procedure inp; inline; var f:text; i,m,u,c,v,l:longint; begin assign(f,FINP); reset(f); read(f,n,m); for i:=1 to n do begin thuan[i]:=nil; nghich[i]:=nil; end; for i:=1 to m do begin read(f,l,u,v,c); add(v,c,thuan[u]); add(u,c,nghich[v]); if l=2 then begin add(u,c,thuan[v]); add(v,c,nghich[u]); end; end; close(f); end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure downHeap(i:longint); inline; var j:longint; begin j:=i shl 1; while (j<=hsize) do begin if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j); if d[h[j]]<d[h[i]] then begin swap(hpos[h[i]],hpos[h[j]]); swap(h[i],h[j]); end; i:=j; j:=i shl 1; end; end; procedure upHeap(i:longint); inline; var j:longint; begin j:=i shr 1; while (i>1) and (d[h[i]]<d[h[j]]) do begin swap(hpos[h[i]],hpos[h[j]]); swap(h[i],h[j]); i:=j; j:=i shr 1; end; end; procedure push(u:longint); inline; begin inc(hsize); h[hsize]:=u; hpos[u]:=hsize; upHeap(hsize); end; procedure pop(var u:longint); inline; begin u:=h[1]; hpos[u]:=0; swap(h[1],h[hsize]); hpos[h[1]]:=1; dec(hsize); downHeap(1); end; procedure dijkstra; inline; var u,v,c:longint; p:list; begin for u:=1 to n do d[u]:=oo; for u:=1 to n do sl[u]:=-1; sl[1]:=1; hsize:=0; d[1]:=0; push(1); while hsize>0 do begin pop(u); p:=thuan[u]; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; if d[v]>d[u]+c then begin d[v]:=d[u]+c; if hpos[v]=0 then push(v) else upHeap(hpos[v]); end; end; end; end; procedure dfs(u:longint); inline; var p:list; v,c:longint; begin if sl[u]<>-1 then exit; sl[u]:=0; p:=nghich[u]; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; if d[v]+c=d[u] then begin dfs(v); sl[u]:=sl[u]+sl[v]; end; end; end; procedure ans; inline; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,d[n],' ',sl[n]); close(f); end; begin inp; dijkstra; dfs(n); ans; end.
Code mẫu của ll931110
Program QBSCHOOL2; Const input = ''; output = ''; max = 200000000; Var u,v,c: array[1..20000] of integer; k: array[1..20000] of byte; d: array[1..5000] of longint; adj,adjcost,h: array[1..40000] of longint; numway: array[1..5000] of int64; free: array[1..5000] of boolean; n,m: integer; Procedure LoadGraph; Var f: text; i,t: longint; Begin Assign(f, input); Reset(f); Fillchar(h, sizeof(h), 0); Readln(f, n, m); For i:= 1 to m do Begin Readln(f, k[i], u[i], v[i], c[i]); inc(h[u[i]]); If k[i] = 2 then inc(h[v[i]]); End; Close(f); For i:= 2 to n do h[i]:= h[i] + h[i - 1]; t:= h[n]; For i:= 1 to m do Begin adj[h[u[i]]]:= v[i]; adjcost[h[u[i]]]:= c[i]; dec(h[u[i]]); If k[i] = 2 then Begin adj[h[v[i]]]:= u[i]; adjcost[h[v[i]]]:= c[i]; dec(h[v[i]]); End; End; h[n + 1]:= t; End; Procedure init; Var i: longint; Begin Fillchar(free, sizeof(free), true); For i:= 1 to n do d[i]:= max; d[1]:= 0; Fillchar(numway, sizeof(numway), 0); numway[1]:= 1; End; Procedure Dijkstra; Var i,u,v,min,iv: longint; Begin Repeat u:= 0; min:= max; For i:= 1 to n do if free[i] and (d[i] < min) then Begin u:= i; min:= d[i]; End; If u = 0 then break; free[u]:= false; For iv:= h[u] + 1 to h[u + 1] do Begin v:= adj[iv]; If free[v] then if d[v] > d[u] + adjcost[iv] then Begin d[v]:= d[u] + adjcost[iv]; numway[v]:= numway[u]; End else if d[v] = d[u] + adjcost[iv] then numway[v]:= numway[v] + numway[u]; End; Until false; End; Procedure solve; Var f: text; Begin Assign(f, output); Rewrite(f); Writeln(f, d[n], ' ', numway[n]); Close(f); End; Begin LoadGraph; init; Dijkstra; solve; End.
Code mẫu của skyvn97
#include<stdio.h> #include<vector> #include<queue> #define MAX 5555 const int INF=1e9; using namespace std; typedef long long ll; typedef pair<int,int> ii; typedef vector<ii> vii; int m,n; vii g[MAX]; ll c[MAX]; int d[MAX]; int s,e; void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); int i,k,u,v,w; for (i=1;i<=m;i=i+1) { scanf("%d",&k); scanf("%d",&u); scanf("%d",&v); scanf("%d",&w); g[u].push_back(ii(v,w)); if (k==2) g[v].push_back(ii(u,w)); } for (i=1;i<=n;i=i+1) { d[i]=INF; c[i]=0; } c[1]=1; d[1]=0; } void dijkstra(void) { int i,v,w; ii x; priority_queue<ii,vii,greater<ii> > q; q.push(ii(0,1)); while (!q.empty()) { x=q.top(); q.pop(); w=x.first; v=x.second; for (i=0;i<g[v].size();i=i+1) { if (d[g[v][i].first]==w+g[v][i].second) { c[g[v][i].first]+=c[v]; continue; } if (d[g[v][i].first]>w+g[v][i].second) { d[g[v][i].first]=w+g[v][i].second; c[g[v][i].first]=c[v]; q.push(ii(d[g[v][i].first],g[v][i].first)); continue; } } } printf("%d %lld",d[n],c[n]); } int main(void) { loadgraph(); dijkstra(); }
Comments