Problem 82

Problem 82 - Project Euler
引き続いて最短経路問題。
データはProblem 81と一緒だけど、開始ノードと目標ノードがそれぞれ複数候補を持っている。こういうときのアルゴリズムってあるのかな。
ちょっと無理矢理問いた感じはあるけどなんとか1分以内には終わった。40秒。

library(igraph)

mtrx <- read.table("matrix.txt",sep=",")
nodeid <- matrix(1:(80*80), 80, 80)
edge <- numeric(0)
weight <- numeric(0)
for(i in 1:79){
  edge <- c(edge,
            nodeid[1,i], nodeid[1,i+1],
            nodeid[1,i], nodeid[1+1,i]
            )
  weight <- c(weight,
              mtrx[1,i+1], mtrx[1+1,i]
              )
  for(j in 2:79){
    edge <- c(edge,
              nodeid[j,i], nodeid[j-1,i],
              nodeid[j,i], nodeid[j,i+1],
              nodeid[j,i], nodeid[j+1,i]
              )
    weight <- c(weight,
                mtrx[j-1,i], mtrx[j,i+1], mtrx[j+1,i]
                )
  }
  edge <- c(edge,
            nodeid[80,i], nodeid[80,i+1],
            nodeid[80,i], nodeid[80-1,i]
            )
  weight <- c(weight,
              mtrx[80,i+1], mtrx[80-1,i]
              )
}
edge <- data.frame(matrix(edge, nc=2, byrow=T))
g <- graph.data.frame(edge,directed=TRUE,
                      vertices=as.vector(nodeid))
E(g)$weight <- weight

sums <- function(a) sum(as.vector(as.matrix(mtrx))[a+1])
ans <- 10000000
for(i in 1:80){
  paths <- get.shortest.paths(g,
                            from=nodeid[i,1]-1,
                            to=nodeid[,80]-1,
                            mode="out"
                            )
  cand <- min(as.numeric(as.matrix(lapply(paths,sums))))
  if(ans>cand) ans <- cand
}
ans