graph:
    proc options(main);
    %replace 
        true     by '1'b,
        false    by '0'b,
        citysize by 20,
        infinite by 32767;
    dcl
        sysin file;
    dcl
        1 city_node based,
          2 city_name   char(citysize) var,
          2 total_dist  fixed,
          2 investigate bit,
          2 city_list   ptr,
          2 route_head  ptr;
    dcl
        1 route_node based,
          2 next_city   ptr,
          2 route_dist  fixed,
          2 route_list  ptr;
    dcl
        city_head ptr;

        do while(true);
        call setup();
        if city_head = null then
            stop;
        call print_all();
        call print_paths();
        call free_all();
        end;

    setup:
        proc;
        dcl
            dist fixed,
            (city1, city2) char(citysize) var;
        on endfile(sysin) go to eof;
        city_head = null;
        put skip list('Type "City1, Dist, City2"');
        put skip;
            do while(true);
            get list(city1, dist, city2);
            call connect(city1, dist, city2);
            call connect(city2, dist, city1);
            end;
        eof:
        end setup;

    connect:
        proc(source_city, dist, dest_city);
        dcl
            source_city char(citysize) var,
            dist fixed,
            dest_city   char(citysize) var;
        dcl
            (r, s, d) ptr;
        s = find(source_city);
        d = find(dest_city);
        allocate route_node set (r);
        r->route_dist = dist;
        r->next_city  = d;
        r->route_list = s->route_head;
        s->route_head = r;
        end connect;

    find:
        proc(city) returns(ptr);
        dcl
            city char(citysize) var;
        dcl
            (p, q) ptr;
            do p = city_head
                repeat(p->city_list) while(p^=null);
            if city = p->city_name then
                return(p);
            end;
        allocate city_node set(p);
        p->city_name  = city;
        p->city_list  = city_head;
        city_head     = p;
        p->total_dist = infinite;
        p->route_head = null;
        return(p);
        end find;

    print_all:
        proc;
        dcl
            (p, q) ptr;
        do p = city_head
            repeat(p->city_list) while(p^=null);
        put skip list(p->city_name,':');
            do q = p->route_head
                repeat(q->route_list) while(q^=null);
            put skip list(q->route_dist,'miles to',
                         q->next_city->city_name);
            end;
        end;
    end print_all;

    print_paths:
        proc;
        dcl
            city char(citysize) var;
        on endfile(sysin) go to eof;
            do while(true);
            put skip list('Type Destination ');
            get list(city);
            call shortest_dist(city);
            on endfile(sysin) go to eol;
                do while(true);
                put skip list('Type Start ');
                get list(city);
                call print_route(city);
                end;
            eol: revert endfile(sysin);
            end;
        eof:
        end print_paths;

    shortest_dist:
        proc(city);
        dcl
            city char(citysize) var;
        dcl
            bestp ptr,
            (d, bestd) fixed,
            (p, q, r) ptr;
            do p = city_head
                repeat(p->city_list) while(p^=null);
            p->total_dist  = infinite;
            p->investigate = false;
            end;
        p = find(city);
        p->total_dist  = 0;
        p->investigate = true;
            do while(true);
            bestp = null;
            bestd = infinite;
                do p = city_head
                    repeat(p->city_list) while(p^=null);
                if p->investigate then
                    do;
                    if p->total_dist < bestd then
                        do;
                        bestd = p->total_dist;
                        bestp = p;
                        end;
                    end;
                end;
            if bestp = null then
                return;
            bestp->investigate = false;
                do q = bestp->route_head
                    repeat(q->route_list) while(q^=null);
                r = q->next_city;
                d = bestd + q->route_dist;
                if d < r->total_dist then
                    do;
                    r->total_dist  = d;
                    r->investigate = true;
                    end;
                end;
            end;
        end shortest_dist;

    print_route:
        proc(city);
        dcl
            city char(citysize) var;
        dcl
            (p, q) ptr,
            (t, d) fixed;
        p = find(city);
            do while(true);
            t = p->total_dist;
            if t = infinite then
                do;
                put skip list('(No Connection)');
                return;
                end;
            if t = 0 then
                return;
            put skip list(t,'miles remain,');
            q = p->route_head;
                do while(q^=null);
                p = q->next_city;
                d = q->route_dist;
                if t = d + p->total_dist then
                    do;
                    put list(d,'miles to',p->city_name);
                    q = null;
                    end; else
                q = q->route_list;
                end;
            end;
        end print_route;

    free_all:
        proc;
        dcl
            (p, q) ptr;
            do p = city_head
                repeat(p->city_list) while(p^=null);
                do q = p->route_head
                    repeat(q->route_list) while(q^=null);
                free q->route_node;
                end;
            free p->city_node;
            end;
        end free_all;

    end graph;