CENTRE28 – SPOJ

Đề bài: http://vn.spoj.com/problems/CENTRE28/

Thuật toán:

• Tìm đường đi ngắn nhất giữa đỉnh 1 đến mọi đỉnh và giữa đỉnh n đến mọi đỉnh sử dụng thuật toán Dijkstra. Đồng thời ta tính số đường đi ngắn nhất.
• Gọi d1[i] là đường đi ngắn nhất từ đỉnh 1 đến i
• Gọi d2[i] là đường đi ngắn nhất từ đỉnh n đến i
• Gọi f1[i] là số đường đi ngắn nhất từ đỉnh 1 đến i
• Gọi f2[i] là số đường đi ngắn nhất từ đỉnh n đến i
• Điều kiện để đỉnh i có thể làm trung tâm kinh tế thứ 3 là: (d1[i]+dn[i]<>d1[n]) hoặc (f1[i]*fn[i]<>f1[n])

Code:

Pascal

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:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        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 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);
        {for i:=1 to n do writeln(d1[i]);}
        writeln(res);
        for i:=1 to res do writeln(ans[i]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++

#include 
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;

using namespace std;
int n, m;
struct data{
    int u, w;
    bool operator <(const data &op) const
    {
        return w > op.w;
    }
};
vector< data > adj[MAXN];
priority_queue > q;
int d[3][MAXN];
long long f[3][MAXN];
void min_path(int cs, int s)
{
    FORE(u, 1, n) d[cs][u] = INF;
    d[cs][s] = 0; f[cs][s] = 1;
    q.push((data){s, 0});
    while (q.size()){
        int u = q.top().u;
        int cost_to_u = q.top().w;
        q.pop();
        if (cost_to_u != d[cs][u]) continue;
        FOR(i, 0, adj[u].size()){
            int v = adj[u][i].u;
            int w = adj[u][i].w;
            if (d[cs][v] > d[cs][u] + w){
                d[cs][v] = d[cs][u] + w;
                f[cs][v] = f[cs][u];
                q.push((data){v, d[cs][v]});
            }
            else
            if (d[cs][v] == d[cs][u] + w) f[cs][v] += f[cs][u];
        }
    }
}
vector< int > ans;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("CENTRE.inp", "r", stdin);
    freopen("CENTRE.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> n >> m;
    int u, v, w;
    FORE(i, 1, m){
        cin >> u >> v >> w;
        adj[u].push_back((data){v, w});
        adj[v].push_back((data){u, w});
    }
    min_path(1, 1);
    min_path(2, n);
    FORE(u, 1, n) if (d[1][u] + d[2][u] > d[1][n] || (d[1][u] + d[2][u] == d[1][n] && 1ll * f[1][u] * f[2][u] < f[1][n])) ans.push_back(u);
    cout << ans.size() << endl;
    FOR(i, 0, ans.size()) cout << ans[i]<