win 7 x64 cpu: i7 3770 ghc: 7.4.2 x32 -O2 -fllvm llvm: 3.1 gcc: 4.5.2 -O3 (нет разницы с -O2) разница в 2.6 раза, из 90 секунд работы хаскель-версии 12% - чтение файла и построение графа в памяти.

bf.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int infinity = 2147483647;

struct edge_t {
    int v1;
    int v2;
    int cost;
};

int
main(void) {
    int nvertex, nedge;

    scanf("%d %d\n", &nvertex, &nedge);

    int nalledges = nedge + nvertex;
    struct edge_t *edges = malloc(nalledges * sizeof(struct edge_t));

    // read input
    for (int i = 0; i < nedge; i++) {
        scanf("%d %d %d\n", &edges[i].v1, &edges[i].v2, &edges[i].cost);
    }
    // add edges from fake vertex
    for (int i = 0; i < nvertex; i++) {
        int idx = nedge + i;
        edges[idx].v1 = 0;
        edges[idx].v2 = i + 1;
        edges[idx].cost = 0;
    }

    int *c1 = malloc((nvertex + 1) * sizeof(int));
    int *c2 = malloc((nvertex + 1) * sizeof(int));

    c1[0] = 0;
    for (int i = 1; i < nvertex + 1; i++) {
        c1[i] = infinity;
    }

    for (int n = 0; n < nvertex + 2; n++) {
        for (int i = 0; i < nalledges; i++) {
            int target = edges[i].v2;
            int newcost = c1[edges[i].v1];

            if (newcost != infinity) {
                newcost += edges[i].cost;
            }
            if (newcost > c1[target]) {
                newcost = c1[target];
            }
            c1[target] = newcost;
        }
        if (n == nvertex) {
            memcpy(c2, c1, (nvertex + 1) * sizeof(int));
        }
    }
/*
    for (int i = 0; i < nvertex + 1; i++) {
        printf("%d\n", c1[i]);
    }
*/
    if (memcmp(c1, c2, (nvertex + 1) * sizeof(int))) {
        printf("Cycle\n");
    } else {
        int v = c1[0];
        for (int i = 1; i < nvertex + 1; i++) {
            if (c1[i] < v) {
                v = c1[i];
            }
        }
        printf("Shortest path %d\n", v);
    }

    return 0;
}

/*
Shortest path -6

real    0m34.498s
user    0m0.030s
sys     0m0.046s
*/

bf.hs

module Main where

import Data.Functor
import qualified Data.Vector.Unboxed as V

type Vertex = Int
type Dist = Int
type Edge = (Vertex, Vertex, Dist)
type EdgeVec = V.Vector Edge
type CostVec = V.Vector Dist

readEdge :: String -> Edge
readEdge s = (v1, v2, w) where 
    [v1, v2, w] = map read . words $ s 

bfStep :: EdgeVec -> CostVec -> CostVec
bfStep edges prev = V.unsafeAccumulate min prev . V.map mincost $ edges where
    mincost :: Edge -> (Int, Dist)
    mincost (s, h, c) = (h, cost s c)
    cost w c | precost == maxBound = maxBound
             | otherwise = precost + c where
        precost = prev `V.unsafeIndex` w
    
mkEdgeVec :: Int -> [String] -> EdgeVec
mkEdgeVec nvert inp = V.unfoldr step (nvert, inp) where
    step (n, s:xs) = Just (readEdge s, (n, xs))
    step (0, []) = Nothing
    step (n, []) = Just ((0, n, 0), (n - 1, []))

main :: IO()
main = do
    header:body <- lines <$> getContents
    let nvert = read . head . words $ header
    let edgelist = mkEdgeVec nvert body

    let bfbase = V.cons 0 . V.replicate nvert $ maxBound
    let bfout = iterate (bfStep edgelist) bfbase !! nvert

    let bfcheck = bfStep edgelist bfout
    let hasCycle = V.or . V.zipWith (/=) bfout $ bfcheck

    putStrLn $ if hasCycle then "Cycle" else show $ V.minimum bfout

-- -6
--   14,493,151,864 bytes allocated in the heap
--      201,474,036 bytes copied during GC
--       13,282,520 bytes maximum residency (135 sample(s))
--        6,266,336 bytes maximum slop
--               35 MB total memory in use (2 MB lost due to fragmentation)

--                                     Tot time (elapsed)  Avg pause  Max pause
--   Gen  0     27357 colls,     0 par    0.50s    0.46s     0.0000s    0.0005s
--   Gen  1       135 colls,     0 par    0.08s    0.04s     0.0003s    0.0009s

--   INIT    time    0.00s  (  0.00s elapsed)
--   MUT     time   89.44s  ( 89.66s elapsed)
--   GC      time    0.58s  (  0.50s elapsed)
--   EXIT    time    0.00s  (  0.00s elapsed)
--   Total   time   90.03s  ( 90.17s elapsed)

--   %GC     time       0.6%  (0.6% elapsed)

--   Alloc rate    162,023,411 bytes per MUT second

--   Productivity  99.4% of total user, 99.2% of total elapsed