Editorial for Traffic Network
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 happyboy99x
#include<cstdio> #include<vector> #include<queue> #include<climits> #include<algorithm> using namespace std; #define N 10000 #define fi first #define se second #define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it) typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; int d[N], rd[N], n, m, k, s, t; vvii g, rg; void enter() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); --s; --t; g = vvii(n, vii()); rg = vvii(n, vii()); for(int i = 0; i < m; ++i) { int u, v, l; scanf("%d%d%d",&u,&v,&l); --u; --v; g[u].push_back(ii(v, l)); rg[v].push_back(ii(u, l)); } } void Dijkstra(const vvii &g, int *d, const int &s) { fill(d, d+n, INT_MAX); d[s] = 0; priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, s)); while(!qu.empty()) { int du = qu.top().fi, u = qu.top().se; 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)); } } } void solve() { Dijkstra(g, d, s); Dijkstra(rg, rd, t); /*for(int i = 0; i < n; ++i) printf("%d ", d[i]); putchar(10); for(int i = 0; i < n; ++i) printf("%d ", rd[i]); putchar(10);*/ int res = d[t]; for(int i = 0; i < k; ++i) { int u, v, l; scanf("%d%d%d", &u, &v, &l); --u; --v; if(d[u] != INT_MAX && rd[v] != INT_MAX) res = min(res, d[u] + rd[v] + l); if(d[v] != INT_MAX && rd[u] != INT_MAX) res = min(res, d[v] + rd[u] + l); //res = min(res, min(d[u] + rd[v] + l, d[v] + rd[u] + l)); } printf("%d\n", res == INT_MAX ? -1 : res); } int main() { #ifdef __DONGOCKHANH__ freopen("input.txt", "r", stdin); #endif int tc; scanf("%d", &tc); while(tc--) { enter(); solve(); } return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> const int N = 10005; const int oo = 1000000009; using namespace std; vector<ii> a[2][N]; int d[2][N], m, n, s, tt, k, t; void Dijkstra(int source, int p) { priority_queue<ii, vector<ii>, greater<ii> > Q; Q.push(ii(0, source)); int i, v, uv, u, du; ii t; for(i=1; i<=n; i++) d[p][i] = oo; d[p][source] = 0; while (Q.size()) { t = Q.top(); Q.pop(); u = t.second; du = t.first; if (du != d[p][u]) continue; for(i=0; i<a[p][u].size(); i++) { v = a[p][u][i].first; uv = a[p][u][i].second; if (d[p][v] > d[p][u] + uv) { d[p][v] = d[p][u] + uv; Q.push(ii(d[p][v], v)); } } } } int main() { //freopen("TRAFFICN.in", "r", stdin); scanf("%d\n", &tt); int i, u, v, c, res; while (tt--) { scanf("%d %d %d %d %d\n", &n, &m, &k, &s, &t); for(i=1; i<=n; i++) {a[0][i].clear();a[1][i].clear();} for(i=1; i<=m; i++) { scanf("%d %d %d\n", &u, &v, &c); a[0][u].push_back(ii(v, c)); a[1][v].push_back(ii(u, c)); } Dijkstra(s, 0); Dijkstra(t, 1); res = d[0][t]; while (k--) { scanf("%d %d %d\n", &u, &v, &c); res = min(res, min(d[0][u] + c + d[1][v], d[0][v] + c+ d[1][u])); } if (res == oo) res = -1; printf("%d\n", res); } return 0; }
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=10111; oo=1000000011; type list=^node; node=record u,c:longint; next:list; end; var f1,f2:text; hsize,ntest,test,n,m,s,t,k:longint; ec,eu,ev:array[1..350] of longint; h,hpos:array[1..MAXN] of longint; d:array[0..1,1..MAXN] of longint; ke,ke2:array[1..MAXN] of list; 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 i,u,v,c:longint; begin read(f1,n,m,k,s,t); fillchar(ke,sizeof(ke),0); fillchar(ke2,sizeof(ke2),0); for i:=1 to m do begin read(f1,u,v,c); add(v,c,ke[u]); add(u,c,ke2[v]); end; for i:=1 to k do read(f1,eu[i],ev[i],ec[i]); end; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure downHeap(cs,i:longint); var j:longint; begin j:=i<<1; while (j<=hsize) do begin if (j<hsize) and (d[cs,h[j+1]]<d[cs,h[j]]) then inc(j); if (d[cs,h[j]]<d[cs,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(cs,i:longint); var j:longint; begin j:=i>>1; while (i>1) and (d[cs,h[i]]<d[cs,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(cs,u:longint); begin inc(hsize); h[hsize]:=u; hpos[u]:=hsize; upHeap(cs,hsize); end; procedure pop(cs:longint; var u:longint); begin u:=h[1]; hpos[u]:=0; swap(h[1],h[hsize]); hpos[h[1]]:=1; dec(hsize); downHeap(cs,1); end; procedure solve; var u,v,c,i,kq:longint; p:list; begin for u:=1 to n do d[0,u]:=oo; d[0,s]:=0; fillchar(hpos,sizeof(hpos),0); hsize:=0; push(0,s); while hsize>0 do begin pop(0,u); p:=ke[u]; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; if d[0,v]>d[0,u]+c then begin d[0,v]:=d[0,u]+c; if hpos[v]=0 then push(0,v) else upHeap(0,hpos[v]); end; end; end; for u:=1 to n do d[1,u]:=oo; d[1,t]:=0; fillchar(hpos,sizeof(hpos),0); hsize:=0; push(1,t); while hsize>0 do begin pop(1,u); p:=ke2[u]; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; if d[1,v]>d[1,u]+c then begin d[1,v]:=d[1,u]+c; if hpos[v]=0 then push(1,v) else upHeap(1,hpos[v]); end; end; end; kq:=min(d[0,t],d[1,s]); for i:=1 to k do begin u:=eu[i]; v:=ev[i]; c:=ec[i]; kq:=min(kq,d[0,u]+d[1,v]+c); kq:=min(kq,d[0,v]+d[1,u]+c); end; if kq=oo then writeln(f2,-1) else writeln(f2,kq); end; begin openF; read(f1,ntest); for test:=1 to ntest do begin inp; solve; end; closeF; end.
Code mẫu của hieult
#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.000000001 #define maxn 10011 #define oo 1111111111 #define modunlo 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) 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; struct canh{ int id,gt; canh(){}; canh(int _id, int _gt){ id = _id; gt = _gt; } }; struct doan{ int chiso,gt; doan(){}; doan(int _chiso,int _gt){ chiso = _chiso; gt = _gt; } bool operator <(const doan D)const{ return gt<D.gt; } }; set<doan> S1,S2; set<doan>::iterator it; int f1[111111],f2[111111]; vector<vector<canh> > V1,V2; int n,m,k,s,t,test; int x,y,c,u,v,uu,vv; int main(){ // freopen("TRAFFICN.in","r",stdin); scanf("%d",&test); for(int itest = 1;itest<=test;itest++){ scanf("%d %d %d %d %d",&n,&m,&k,&s,&t); V1.clear(); V2.clear(); V1.resize(n+3); V2.resize(n+3); memset(f1,-1,sizeof(f1)); memset(f2,-1,sizeof(f2)); for(int i = 0;i<m;i++){ scanf("%d %d %d",&x,&y,&c); V1[x].push_back(canh(y,c)); V2[y].push_back(canh(x,c)); } S1.clear(); S1.insert(doan(s,0)); while(S1.size()){ it = S1.begin(); u = (*it).chiso; v = (*it).gt; S1.erase(S1.begin()); if(f1[u]==-1){ f1[u] = v; TR(V1[u],it){ uu = (*it).id; vv = (*it).gt; if(f1[uu]==-1){ S1.insert(doan(uu,v+vv)); } } } } S2.clear(); S2.insert(doan(t,0)); while(S2.size()){ it = S2.begin(); u = (*it).chiso; v = (*it).gt; S2.erase(S2.begin()); if(f2[u]==-1){ f2[u] = v; TR(V2[u],it){ uu = (*it).id; vv = (*it).gt; if(f2[uu]==-1) S2.insert(doan(uu,v+vv)); } } } // for(int i = 1;i<=n;i++) printf("%d %d\n",f1[i],f2[i]); int kq = oo; if(f1[t]!=-1) kq = f1[t]; for(int i = 0;i<k;i++){ scanf("%d %d %d",&x,&y,&c); if(f1[x]!=-1 && f2[y]!=-1) kq = min(kq,f1[x]+f2[y]+c); if(f1[y]!=-1 && f2[x]!=-1) kq = min(kq,f1[y]+f2[x]+c); } if(kq<oo) printf("%d\n",kq); else printf("-1\n"); } // getch(); }
Code mẫu của ll931110
Program TRAFFICN; Const input = ''; output = ''; maxn = 10000; maxm = 100000; maxv = 1000000000; Type arrn = array[1..maxn + 1] of longint; arrm = array[1..maxm + 1] of longint; Var h,hs,ht,heap,pos: arrn; d,ds,dt: arrn; adj,adjcost: arrm; adjs,adjcosts: arrm; adjt,adjcostt: arrm; x,y,c: arrm; free: array[1..maxn] of boolean; n,m,k,s,t: longint; test,i: integer; nHeap: longint; fi,fo: text; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure LoadGraph; Var i: longint; Begin Fillchar(hs, sizeof(hs), 0); Fillchar(ht, sizeof(ht), 0); Readln(fi, n, m, k, s, t); For i:= 1 to m do Begin Readln(fi, x[i], y[i], c[i]); inc(hs[x[i]]); inc(ht[y[i]]); End; For i:= 2 to n do hs[i]:= hs[i] + hs[i - 1]; For i:= 2 to n do ht[i]:= ht[i] + ht[i - 1]; For i:= 1 to m do Begin adjs[hs[x[i]]]:= y[i]; adjcosts[hs[x[i]]]:= c[i]; dec(hs[x[i]]); adjt[ht[y[i]]]:= x[i]; adjcostt[ht[y[i]]]:= c[i]; dec(ht[y[i]]); End; hs[n + 1]:= m; ht[n + 1]:= m; End; Procedure update(v: longint); Var parent,child: longint; Begin child:= pos[v]; If child = 0 then Begin inc(nHeap); child:= nHeap; End; parent:= child div 2; While (parent > 0) and (d[heap[parent]] > d[v]) do Begin heap[child]:= heap[parent]; pos[heap[child]]:= child; child:= parent; parent:= child div 2; End; heap[child]:= v; pos[v]:= child; End; Function pop: longint; Var r,c,v: longint; Begin pop:= heap[1]; v:= heap[nHeap]; dec(nHeap); r:= 1; While r * 2 <= nHeap do Begin c:= r * 2; If (c <= nHeap) and (d[heap[c + 1]] < d[heap[c]]) then inc(c); If d[v] <= d[heap[c]] then break; heap[r]:= heap[c]; pos[heap[r]]:= r; r:= c; End; heap[r]:= v; pos[v]:= r; End; Procedure Dijkstra(s: longint); Var u,v,i,iv: longint; Begin nHeap:= 0; Fillchar(pos, sizeof(pos), 0); Fillchar(free, sizeof(free), true); For i:= 1 to n do d[i]:= maxv; d[s]:= 0; update(s); Repeat u:= pop; free[u]:= false; For iv:= h[u] + 1 to h[u + 1] do Begin v:= adj[iv]; If free[v] and (d[v] > d[u] + adjcost[iv]) then Begin d[v]:= d[u] + adjcost[iv]; update(v); End; End; Until nHeap = 0; End; Procedure solve; Var i,minway: longint; u,v,cost: longint; tmp: longint; Begin h:= hs; adj:= adjs; adjcost:= adjcosts; Dijkstra(s); ds:= d; h:= ht; adj:= adjt; adjcost:= adjcostt; Dijkstra(t); dt:= d; minway:= ds[t]; For i:= 1 to k do Begin Readln(fi, u, v, cost); tmp:= ds[u] + dt[v] + cost; If minway > tmp then minway:= tmp; tmp:= ds[v] + dt[u] + cost; If minway > tmp then minway:= tmp; End; If minway = maxv then writeln(fo, -1) else writeln(fo, minway); End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; Readln(fi, test); For i:= 1 to test do Begin LoadGraph; solve; End; closefile; End.
Code mẫu của skyvn97
#include<cstdio> #include<cstring> #include<queue> #include<vector> #define MAX 10010 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) #define fi first #define se second using namespace std; typedef pair<int,int> ii; const int INF=(int)1e9+7; vector<ii> gf[MAX],gb[MAX],ga[MAX]; int d[3][MAX]; int m,n,k,s,t; void minimize(int &x,const int &y) { if (x>y) x=y; } void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); scanf("%d",&k); scanf("%d",&s); scanf("%d",&t); FOR(i,1,n) { gf[i].clear(); gb[i].clear(); ga[i].clear(); } REP(i,m) { int u,v,w; scanf("%d",&u); scanf("%d",&v); scanf("%d",&w); gf[u].push_back(ii(v,w)); gb[v].push_back(ii(u,w)); } REP(i,k) { int u,v,w; scanf("%d",&u); scanf("%d",&v); scanf("%d",&w); ga[u].push_back(ii(v,w)); ga[v].push_back(ii(u,w)); } memset(d,0x3f,sizeof d); } void dijkstra(int s,vector<ii> g[],int d[]) { priority_queue<ii,vector<ii>,greater<ii> > q; while (!q.empty()) q.pop(); d[s]=0; q.push(ii(0,s)); while (!q.empty()) { int u=q.top().se; int w=q.top().fi; q.pop(); FORE(it,g[u]) if (w+it->se<d[it->fi]) { d[it->fi]=w+it->se; q.push(ii(d[it->fi],it->fi)); } } } void process(void) { dijkstra(s,gf,d[0]); dijkstra(t,gb,d[1]); int res=d[0][t]; FOR(i,1,n) FORE(j,ga[i]) minimize(res,d[0][i]+j->se+d[1][j->fi]); if (res>=INF) printf("-1\n"); else printf("%d\n",res); } int main(void) { #ifndef ONLINE_JUDGE freopen("tmp.txt","r",stdin); #endif int tc; scanf("%d",&tc); REP(ct,tc) { loadgraph(); process(); } return 0; }
Code mẫu của khuc_tuan
// {$APPTYPE CONSOLE} {$mode delphi} uses math, sysutils; type PData = ^Data; Data = record v, c : integer; n : PData; end; ArrData = array[1..10000] of PData; ArrInt = array[1..10000] of integer; procedure Add( var d : PData; v, c : integer); var p : PData; begin new(p); p.v := v; p.c := c; p.n := d; d := p; end; var m, n : integer; s, t : integer; ke, ken : ArrData; ds, dt : ArrInt; h, pos : ArrInt; nh : integer; procedure pushdown(i : integer; var d : ArrInt); var j, t : integer; begin while 2*i <= nh do begin j := 2 * i; if (j<nh) and (d[h[j+1]] < d[h[j]]) then inc(j); if d[h[j]] < d[h[i]] then begin t := h[i]; h[i] := h[j]; h[j] := t; pos[h[i]] := i; pos[h[j]] := j; i := j; end else break; end; end; procedure pushup(i : integer; var d : ArrInt); var j, t : integer; begin while i >= 2 do begin j := i div 2; if d[h[j]] > d[h[i]] then begin t := h[i]; h[i] := h[j]; h[j] := t; pos[h[i]] := i; pos[h[j]] := j; i := j; end else break; end; end; procedure addheap(i : integer; var d : ArrInt); begin inc(nh); h[nh] := i; pos[i] := nh; pushup(nh, d); end; function extractmin(var d : ArrInt) : integer; begin extractmin := h[1]; h[1] := h[nh]; dec(nh); pos[h[1]] := 1; pushdown(1, d); end; procedure dijkstra(var ke : ArrData; s : integer; var d : ArrInt); var k, u, v, i : integer; p : PData; begin for i:=1 to n do d[i] := 1000000000; fillchar( pos, sizeof(pos), -1); d[s] := 0; nh := 0; addheap(s, d); while nh > 0 do begin u := extractmin(d); p := ke[u]; while p<>nil do begin v := p.v; if d[v] > d[u] + p.c then begin d[v] := d[u] + p.c; if pos[v]=-1 then addheap( v, d) else begin k := pos[v]; pushup(k, d); end; end; p := p.n; end; end; end; var k, j, u, v, c, st, kk : integer; res : integer; begin read(st); for kk:=1 to st do begin read(n, m, k, s, t); for j:=1 to n do begin ke[j] := nil; ken[j] := nil; end; for j:=1 to m do begin read(u,v,c); Add(ke[u], v, c); Add(ken[v], u, c); end; dijkstra(ke, s, ds); dijkstra(ken, t, dt); res := ds[t]; for j:=1 to k do begin read(u,v,c); res := min( res, ds[u] + dt[v] + c); res := min( res, ds[v] + dt[u] + c); end; if res = 1000000000 then writeln(-1) else writeln(res); end; end.
Comments