Problem 83

Problem 83 - Project Euler
またまた最短経路。

This problem is a significantly more challenging version of Problem 81.

と書いてあるけどProblem 81のに3行足すだけで終わってしまった…。
これ例えばダイクストラのアルゴリズムを自分で実装したとしてもやっぱりProblem 81に3行足すだけで終わるような気がするんだけどどのあたりが挑戦しがいのある問題なんだろう。

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:80){
  for(j in 1:79){
    edge <- c(edge,
              nodeid[i,j], nodeid[i,j+1],
              nodeid[j,i], nodeid[j+1,i],
              nodeid[i,j+1], nodeid[i,j],
              nodeid[j+1,i], nodeid[j,i]
              )
    weight <- c(weight,
                mtrx[i,j+1], mtrx[j+1,i],
                mtrx[i,j], mtrx[j,i])
  }
}
edge <- data.frame(matrix(edge,nc=2,byrow=T))
g <- graph.data.frame(edge,directed=TRUE,
                      vertices=as.vector(nodeid))
ans <- get.shortest.paths(g,from=0,to=6399,mode="out",
                          weights=weight)[[1]]
sum(as.vector(as.matrix(mtrx))[ans+1])