Đề bài:
Thuật toán:
- Gọi Gọi f[i] và d[i] lần lượt là độ dài và số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.
- Để tính d[i] ta sử dụng thuật toán Dijkstra
- Để tính số lượng đường đi ngắn nhất giữa hai đỉnh ta tính như sau
Nếu d[v]>d[u]+c(u,v), ta gán d[v]=d[u]+c(u,v) và f[v]=f[u]
Nếu d[v]=d[u]+c(u,v) thì gán f[v]=f[v]+f[u].
(có thể xem rõ hơn ở code bên dưới)
Code:
- Pascal : https://ideone.com/hzQr1z
- C++ : https://ideone.com/ELwAFE
const fi =''; fo =''; maxn =30000+3; maxc =trunc(1e9)+3; maxm =trunc(1e5); type arrd =array[1..maxn] of longint; arrf =array[1..maxn] of int64; arrk =array[-maxm..maxm] of longint; arrh =array[1..maxn] of longint; var d1,dn,d :arrd; f1,fn,f :arrf; n,i,j,m :longint; res :longint; ans :arrd; head :array[1..maxn] of longint; link,ts,ke :arrk; // dijkstra heap; h,p :array[1..maxn] of longint; nh :longint; procedure add(i,u,v,w:longint); begin link[i]:=head[u]; head[u]:=i; ke[i]:=v; ts[i]:=w; end; procedure enter; var u,v,w,k:longint; begin assign(input,fi);reset(input); readln(n,m); for i:=1 to m do begin read(k,u,v,w); add(i,u,v,w); if k=2 then add(-i,v,u,w); end; close(input); end; procedure swap(var x,y:longint); var tg:longint; begin tg:=x;x:=y;y:=tg; end; procedure upheap(i:longint); var j:longint; begin j:=i div 2; if i>1 then if d[h[i]] < d[h[j]] then begin swap(h[i],h[j]); swap(p[h[i]],p[h[j]]); upheap(j); end; end; procedure downheap(i:longint); var j:longint; begin j:=i + i; if j>nh then exit; if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j); if d[h[j]] < d[h[i]] then begin swap(h[i],h[j]); swap(p[h[i]],p[h[j]]); downheap(j); end; end; procedure push(i:longint); begin inc(nh); h[nh]:=i; p[i]:=nh; upheap(nh); end; function pop:longint; begin pop:=h[1]; h[1]:=h[nh]; p[h[1]]:=1; dec(nh); downheap(1); end; procedure update(i:longint); begin if p[i]=0 then push(i) else upheap(p[i]); end; procedure dijkstra(s:longint); var u,v,i:longint; begin fillchar(h,sizeof(f),0); fillchar(p,sizeof(p),0); nh:=0; fillchar(f,sizeof(f),0); for i:=1 to n do d[i]:=maxc; d[s]:=0; f[s]:=1; push(s); repeat u:=pop; i:=head[u]; while i<>0 do begin v:=ke[i]; if d[v]>d[u]+ts[i] then begin d[v]:=d[u]+ts[i]; f[v]:=f[u]; update(v); end else if d[v]=d[u]+ts[i] then begin f[v]:=f[u]+f[v]; end; i:=link[i]; end; until nh=0; end; procedure process; begin dijkstra(1); f1:=f; d1:=d; dijkstra(n); fn:=f; dn:=d; for i:=1 to n do if (d1[i]+dn[i]<>d1[n]) or (f1[i]*fn[i]<>f1[n]) then begin inc(res); ans[res]:=i; end; end; procedure print; begin assign(output,fo);rewrite(output); writeln(d1[n],' ',f1[n]); close(output); end; begin enter; process; print; end. |
#include <iostream> #include <queue> #include <vector> #include <cstring> using namespace std; typedef pair<long long, int> lli; const long long oo = ((1 << 30)-1)*2-1; const int max_n = 5000+1; int n, m; long long min_d, dist = 0, f[max_n]; vector<lli> adj[max_n]; inline void load_map() { cin >> n >> m; int type, u, v, w; while (m--) { cin >> type >> u >> v >> w; adj[u].push_back(lli(w, v)); if (type==2) adj[v].push_back(lli(w, u)); } } inline void dijkstra() { vector<lli>::iterator it; long long cuv, du, d[max_n]; int u, v; priority_queue<lli, vector<lli>, greater<lli> > heap; for (u=1; u <= n; u++) d[u] = +oo; memset(f, 0, sizeof(f)); d[1] = 0; f[1] = 1; heap.push(lli(0, 1)); while (heap.size()) { du = heap.top().first; u = heap.top().second; heap.pop(); if (du != d[u]) continue; if (u == n) break; for (it=adj[u].begin(); it != adj[u].end(); it++) { cuv = it->first; v = it->second; if (d[v]==d[u]+cuv) f[v] += f[u]; if (d[v] > d[u]+cuv) { d[v] = d[u]+cuv; f[v] = f[u]; heap.push(lli(d[v], v)); } } } min_d = d[n]; } main() { load_map(); dijkstra(); cout << min_d << " " << f[n]; } |
Speak Your Mind