Roadblocks R本の道とN個の交差点がある街があります。道路は両方向に通行可能です。1番目の交差点からN番目の交差点への最短経路の長さを求めなさい。ただし、二番目の最短経路とは、最短経路よりも真に長いもののうちで最短のもののことを言います。同じ経路を複数回通っても構いません。 制約 1 ≦ N ≦ 5000 1 ≦ R ≦ 100000 入力 EDGEは(交差点1, 交差点2, 距離の形式で書かれる) N=4 R=4 EDGE= (1, 2, 100), (2, 3, 250), (2, 4,200), (3, 4,100)

Roadblocks.scala

import scala.collection.mutable

object Roadblocks {

  case class Road(from:Int, to:Int, distance:Int)
  case class Next(position:Int,totalDistance:Int)

  def main(args: Array[String]) {
//    val crossPointNumber = 4
//    var edgeCount = 4
//    val edges = Seq((1, 2, 100), (2, 3, 250), (2, 4,200), (3, 4,100))
    val crossPointNumber = 500
    var edgeCount = 1059
    val edges = Seq((1, 4, 385),(1, 2, 179),(2, 6, 136),(2, 3, 304),(3, 4, 421),(3, 7, 438),(3, 5, 418),(4, 6, 453),(4, 9, 429),(5, 8, 423),(5, 7, 115),(6, 11, 291),(6, 10, 124),(7, 11, 424),(7, 8, 112),(8, 9, 114),(8, 12, 301),(9, 14, 174),(9, 11, 116),(9, 10, 151),(10, 15, 310),(10, 11, 130),(10, 13, 299),(11, 13, 347),(12, 17, 109),(12, 16, 286),(13, 17, 304),(13, 15, 223),(13, 14, 164),(14, 17, 413),(14, 15, 153),(15, 18, 457),(15, 17, 123),(16, 19, 300),(17, 20, 253),(17, 18, 434),(18, 21, 352),(18, 20, 364),(19, 24, 343),(19, 22, 131),(19, 21, 492),(20, 21, 265),(21, 26, 482),(21, 22, 410),(22, 24, 185),(22, 23, 411),(22, 25, 377),(23, 24, 220),(23, 26, 384),(23, 25, 299),(24, 26, 477),(24, 28, 441),(24, 27, 464),(25, 30, 227),(25, 27, 223),(26, 28, 182),(26, 30, 489),(27, 32, 252),(27, 28, 152),(28, 31, 281),(28, 30, 498),(28, 32, 427),(29, 34, 198),(30, 33, 184),(30, 32, 157),(31, 35, 155),(31, 34, 407),(32, 34, 429),(32, 33, 107),(33, 38, 341),(33, 37, 136),(34, 36, 368),(34, 35, 376),(34, 38, 104),(35, 40, 403),(35, 39, 178),(35, 37, 345),(36, 37, 134),(37, 42, 221),(37, 40, 127),(38, 41, 368),(38, 43, 495),(39, 40, 288),(39, 41, 176),(40, 41, 336),(40, 43, 373),(41, 45, 168),(41, 42, 225),(42, 47, 178),(42, 46, 181),(42, 45, 476),(43, 44, 183),(43, 47, 173),(43, 48, 454),(44, 47, 222),(44, 45, 325),(45, 50, 122),(45, 49, 206),(46, 51, 335),(46, 48, 304),(46, 47, 234),(47, 48, 192),(47, 50, 335),(48, 51, 367),(48, 53, 358),(48, 52, 397),(49, 52, 138),(49, 53, 266),(49, 54, 193),(50, 51, 370),(50, 53, 318),(50, 55, 120),(51, 55, 494),(51, 52, 178),(52, 57, 174),(52, 54, 224),(52, 55, 114),(53, 58, 434),(53, 54, 234),(53, 56, 210),(54, 57, 158),(54, 58, 184),(55, 56, 456),(55, 57, 409),(56, 58, 340),(56, 59, 163),(57, 60, 117),(57, 61, 382),(57, 62, 205),(58, 63, 314),(58, 62, 246),(59, 62, 145),(60, 65, 237),(60, 61, 408),(61, 63, 315),(61, 62, 160),(62, 67, 122),(62, 65, 250),(63, 68, 429),(63, 65, 363),(64, 65, 123),(64, 69, 347),(65, 69, 333),(65, 67, 104),(66, 71, 341),(67, 72, 454),(67, 71, 286),(67, 70, 145),(68, 69, 329),(69, 70, 335),(69, 73, 150),(69, 71, 494),(70, 73, 265),(70, 72, 329),(71, 74, 299),(71, 73, 205),(72, 76, 494),(72, 74, 433),(73, 78, 400),(74, 78, 159),(74, 76, 467),(75, 80, 158),(75, 77, 455),(76, 77, 122),(76, 79, 343),(77, 78, 277),(77, 80, 239),(78, 79, 106),(78, 82, 126),(78, 80, 371),(79, 84, 311),(79, 82, 330),(79, 80, 394),(80, 81, 256),(80, 82, 195),(81, 85, 345),(81, 83, 301),(82, 84, 349),(83, 84, 240),(83, 88, 424),(83, 85, 190),(84, 86, 325),(84, 85, 448),(85, 90, 285),(85, 89, 288),(86, 89, 118),(86, 91, 285),(87, 89, 219),(87, 90, 119),(88, 89, 128),(89, 94, 270),(89, 91, 163),(89, 92, 333),(90, 92, 305),(90, 91, 284),(90, 95, 395),(91, 93, 131),(91, 94, 454),(92, 95, 430),(93, 97, 136),(93, 98, 434),(93, 95, 292),(94, 97, 363),(94, 98, 224),(95, 100, 292),(95, 98, 467),(96, 100, 348),(96, 99, 131),(96, 101, 301),(97, 100, 120),(97, 101, 294),(98, 101, 115),(98, 102, 398),(98, 99, 267),(99, 102, 496),(99, 100, 225),(100, 105, 451),(100, 103, 104),(100, 102, 443),(101, 103, 275),(101, 104, 257),(102, 105, 145),(102, 107, 437),(103, 107, 247),(103, 106, 233),(103, 105, 419),(104, 109, 396),(105, 109, 227),(105, 106, 368),(106, 110, 303),(106, 107, 271),(107, 110, 376),(108, 113, 343),(108, 110, 356),(109, 112, 109),(109, 113, 217),(110, 113, 130),(110, 112, 396),(111, 115, 360),(111, 114, 267),(112, 116, 296),(113, 118, 169),(113, 114, 467),(114, 119, 411),(114, 117, 350),(115, 119, 416),(115, 120, 213),(116, 117, 281),(117, 120, 110),(117, 119, 488),(118, 120, 476),(118, 121, 189),(119, 120, 262),(119, 122, 402),(120, 124, 389),(120, 125, 370),(121, 123, 130),(122, 123, 477),(122, 124, 253),(122, 126, 291),(123, 128, 156),(123, 126, 124),(124, 126, 488),(124, 127, 430),(125, 128, 437),(125, 127, 103),(126, 129, 183),(126, 131, 130),(127, 131, 338),(127, 130, 147),(128, 130, 114),(128, 132, 100),(129, 133, 366),(129, 134, 126),(129, 132, 366),(130, 134, 268),(131, 135, 245),(131, 136, 144),(132, 136, 156),(132, 137, 271),(133, 138, 112),(133, 134, 200),(134, 137, 375),(135, 138, 400),(135, 139, 301),(136, 138, 451),(136, 140, 138),(136, 137, 346),(137, 139, 136),(137, 141, 463),(138, 142, 152),(138, 143, 383),(138, 140, 138),(139, 140, 140),(139, 144, 206),(139, 143, 247),(140, 142, 371),(140, 143, 280),(141, 145, 487),(141, 143, 342),(142, 146, 460),(142, 145, 115),(143, 146, 259),(143, 145, 301),(144, 148, 300),(144, 146, 279),(145, 150, 192),(145, 148, 103),(145, 147, 337),(146, 150, 225),(146, 151, 326),(146, 149, 429),(147, 148, 177),(147, 149, 144),(147, 151, 224),(148, 153, 314),(148, 151, 303),(149, 153, 379),(149, 150, 443),(149, 154, 105),(150, 153, 426),(150, 152, 153),(151, 155, 242),(151, 154, 127),(151, 156, 153),(152, 154, 180),(152, 157, 125),(153, 155, 421),(153, 157, 203),(154, 159, 317),(155, 157, 134),(155, 158, 214),(156, 158, 357),(156, 161, 312),(157, 159, 446),(157, 161, 486),(157, 162, 206),(158, 159, 327),(159, 160, 302),(159, 163, 281),(159, 161, 377),(160, 163, 263),(160, 161, 299),(161, 164, 382),(161, 166, 116),(161, 162, 450),(162, 163, 201),(162, 165, 494),(163, 167, 138),(163, 164, 112),(164, 167, 315),(165, 168, 359),(165, 169, 335),(166, 171, 368),(166, 170, 298),(166, 168, 330),(167, 169, 266),(167, 170, 461),(168, 169, 296),(168, 170, 173),(169, 171, 209),(169, 172, 216),(170, 175, 259),(170, 174, 186),(171, 176, 431),(172, 175, 291),(172, 174, 124),(173, 174, 410),(173, 178, 260),(173, 177, 366),(174, 175, 421),(174, 178, 131),(175, 176, 433),(175, 177, 209),(176, 180, 244),(176, 179, 151),(177, 178, 442),(177, 180, 197),(178, 181, 446),(178, 179, 267),(179, 180, 315),(179, 184, 182),(180, 184, 420),(180, 185, 292),(181, 185, 193),(181, 183, 179),(182, 184, 142),(182, 187, 247),(183, 184, 393),(183, 186, 289),(184, 189, 100),(184, 186, 312),(184, 188, 260),(185, 188, 115),(185, 190, 155),(185, 186, 271),(186, 188, 115),(186, 189, 497),(187, 192, 421),(188, 193, 167),(188, 192, 388),(188, 190, 365),(189, 190, 244),(189, 194, 249),(190, 193, 430),(190, 192, 163),(191, 192, 290),(191, 194, 102),(191, 193, 356),(192, 193, 451),(192, 197, 193),(193, 194, 335),(193, 197, 104),(193, 196, 313),(194, 195, 221),(194, 196, 214),(195, 198, 307),(195, 197, 156),(196, 200, 480),(197, 202, 397),(197, 201, 463),(198, 199, 482),(198, 200, 465),(198, 202, 391),(199, 203, 495),(199, 202, 460),(199, 204, 420),(200, 202, 102),(200, 203, 164),(201, 202, 417),(201, 203, 116),(201, 206, 342),(202, 206, 129),(202, 203, 302),(203, 207, 117),(203, 208, 246),(204, 205, 365),(204, 207, 471),(204, 208, 100),(205, 209, 440),(205, 207, 253),(205, 206, 414),(206, 208, 245),(206, 210, 484),(207, 208, 291),(207, 212, 456),(208, 212, 197),(208, 211, 277),(209, 210, 363),(209, 212, 447),(209, 214, 477),(210, 212, 135),(210, 213, 114),(210, 215, 308),(211, 212, 483),(211, 216, 191),(211, 215, 207),(212, 214, 264),(213, 214, 168),(213, 218, 276),(214, 215, 416),(214, 216, 163),(214, 217, 223),(215, 219, 448),(215, 220, 488),(216, 219, 442),(216, 217, 470),(217, 218, 228),(217, 221, 416),(217, 222, 386),(218, 221, 463),(218, 219, 419),(219, 221, 353),(220, 224, 397),(220, 223, 425),(220, 221, 237),(221, 223, 397),(221, 222, 345),(222, 226, 216),(222, 224, 450),(223, 227, 280),(224, 225, 365),(224, 227, 490),(225, 227, 490),(226, 227, 461),(226, 228, 191),(227, 229, 351),(227, 231, 149),(228, 230, 190),(228, 231, 404),(228, 232, 479),(229, 234, 203),(229, 232, 407),(230, 233, 455),(230, 232, 346),(231, 235, 259),(231, 233, 384),(232, 236, 329),(232, 233, 457),(233, 235, 228),(233, 236, 174),(234, 237, 479),(234, 238, 293),(235, 236, 300),(235, 237, 232),(235, 240, 388),(236, 238, 399),(236, 241, 193),(237, 239, 438),(237, 240, 368),(237, 242, 330),(238, 241, 343),(238, 242, 173),(239, 240, 281),(239, 243, 426),(239, 242, 430),(240, 244, 111),(240, 245, 121),(240, 241, 485),(241, 245, 337),(241, 243, 237),(241, 242, 154),(242, 245, 407),(242, 244, 221),(243, 245, 472),(243, 247, 133),(243, 244, 186),(244, 247, 368),(244, 246, 267),(245, 247, 364),(245, 248, 427),(246, 248, 346),(246, 247, 366),(247, 250, 173),(247, 251, 473),(248, 249, 475),(248, 252, 202),(248, 251, 375),(249, 254, 193),(250, 255, 398),(250, 253, 339),(251, 256, 449),(252, 255, 473),(252, 254, 335),(252, 256, 320),(253, 258, 196),(253, 255, 449),(254, 257, 326),(255, 257, 273),(255, 260, 238),(256, 261, 155),(256, 260, 195),(257, 259, 393),(258, 260, 197),(258, 262, 304),(259, 262, 278),(259, 261, 213),(260, 262, 468),(260, 265, 397),(261, 263, 382),(261, 266, 172),(262, 267, 106),(262, 263, 336),(263, 266, 486),(263, 268, 431),(264, 265, 484),(264, 267, 125),(265, 268, 418),(265, 270, 142),(266, 267, 420),(267, 269, 238),(267, 271, 211),(268, 271, 396),(268, 272, 193),(269, 274, 277),(269, 270, 469),(270, 274, 200),(270, 273, 451),(271, 272, 345),(271, 275, 138),(272, 274, 144),(272, 277, 291),(273, 274, 353),(273, 275, 408),(274, 279, 369),(274, 277, 398),(274, 278, 209),(275, 278, 437),(275, 276, 285),(276, 277, 454),(277, 280, 371),(277, 282, 493),(278, 283, 437),(278, 281, 270),(279, 282, 293),(279, 284, 199),(279, 280, 426),(280, 284, 381),(280, 285, 428),(280, 282, 115),(281, 283, 142),(281, 282, 227),(282, 285, 310),(282, 283, 498),(282, 286, 235),(283, 286, 258),(283, 284, 243),(284, 287, 119),(284, 286, 308),(285, 289, 128),(285, 290, 477),(286, 290, 171),(286, 289, 367),(287, 290, 490),(287, 291, 378),(288, 293, 455),(288, 290, 348),(289, 292, 281),(289, 291, 265),(290, 293, 129),(290, 292, 353),(291, 294, 158),(291, 295, 260),(292, 295, 442),(293, 294, 409),(293, 295, 141),(293, 298, 275),(294, 296, 169),(294, 298, 410),(294, 295, 122),(295, 299, 470),(295, 297, 300),(296, 298, 291),(297, 301, 197),(297, 299, 185),(297, 300, 328),(298, 300, 425),(298, 299, 349),(298, 302, 145),(299, 303, 309),(299, 300, 186),(300, 305, 148),(300, 302, 241),(301, 303, 459),(301, 306, 187),(301, 302, 334),(302, 305, 471),(302, 304, 208),(302, 306, 464),(303, 304, 278),(304, 306, 408),(304, 308, 183),(304, 309, 146),(305, 307, 296),(305, 309, 366),(306, 308, 386),(306, 310, 263),(307, 310, 403),(307, 309, 138),(307, 311, 167),(308, 312, 299),(308, 313, 234),(309, 312, 493),(309, 313, 378),(310, 314, 260),(310, 313, 298),(311, 315, 413),(311, 314, 105),(311, 313, 309),(312, 314, 131),(312, 317, 346),(312, 316, 181),(313, 318, 404),(313, 315, 322),(313, 314, 243),(314, 319, 261),(314, 317, 125),(315, 317, 482),(315, 318, 147),(316, 319, 461),(316, 320, 351),(316, 318, 109),(317, 318, 132),(317, 322, 442),(318, 320, 115),(318, 323, 140),(318, 322, 385),(319, 321, 341),(319, 323, 299),(320, 322, 437),(320, 321, 420),(321, 324, 108),(321, 326, 409),(322, 327, 166),(322, 325, 269),(323, 327, 201),(324, 328, 164),(324, 326, 380),(325, 327, 303),(325, 326, 166),(326, 330, 341),(326, 327, 251),(327, 331, 304),(327, 332, 170),(328, 329, 309),(328, 331, 126),(328, 330, 474),(329, 332, 485),(329, 330, 496),(330, 332, 420),(330, 335, 106),(331, 334, 264),(331, 336, 232),(332, 333, 321),(333, 334, 366),(333, 338, 222),(334, 336, 369),(335, 340, 176),(335, 338, 414),(336, 341, 320),(336, 339, 434),(337, 338, 102),(337, 340, 439),(338, 342, 288),(339, 343, 164),(339, 342, 170),(339, 341, 298),(340, 343, 295),(340, 342, 330),(341, 344, 499),(342, 346, 316),(342, 344, 221),(343, 347, 265),(343, 345, 233),(344, 347, 386),(344, 346, 349),(345, 347, 301),(345, 349, 157),(346, 349, 362),(346, 348, 140),(347, 348, 190),(347, 350, 168),(348, 349, 182),(348, 352, 210),(349, 350, 356),(349, 352, 324),(350, 355, 474),(350, 354, 148),(351, 354, 247),(351, 355, 240),(352, 357, 309),(352, 355, 442),(352, 356, 326),(353, 357, 306),(353, 354, 430),(353, 355, 168),(354, 358, 255),(354, 359, 444),(355, 359, 345),(355, 358, 200),(356, 357, 178),(356, 358, 460),(357, 358, 163),(357, 360, 464),(358, 363, 344),(358, 359, 160),(359, 361, 177),(359, 364, 365),(359, 360, 352),(360, 364, 148),(360, 365, 136),(361, 362, 350),(361, 365, 215),(362, 365, 253),(363, 368, 161),(363, 365, 187),(364, 365, 375),(364, 367, 148),(364, 366, 272),(365, 369, 171),(365, 366, 423),(366, 371, 193),(367, 370, 244),(367, 372, 372),(368, 373, 434),(368, 370, 296),(368, 369, 228),(369, 370, 164),(369, 374, 411),(370, 371, 417),(370, 372, 288),(371, 376, 128),(371, 372, 181),(372, 375, 282),(372, 374, 196),(373, 377, 296),(373, 378, 409),(374, 379, 310),(375, 379, 494),(376, 377, 445),(376, 379, 495),(377, 382, 252),(377, 381, 250),(378, 383, 281),(378, 382, 104),(378, 380, 332),(379, 384, 179),(379, 383, 106),(380, 382, 315),(380, 381, 247),(380, 384, 159),(381, 385, 490),(381, 386, 370),(382, 383, 196),(383, 384, 203),(384, 386, 300),(384, 385, 193),(384, 389, 450),(385, 390, 138),(385, 386, 188),(386, 389, 367),(386, 387, 375),(387, 392, 149),(387, 389, 497),(387, 390, 172),(388, 391, 421),(388, 393, 343),(389, 394, 483),(389, 392, 308),(390, 395, 445),(390, 394, 256),(391, 396, 126),(391, 393, 494),(392, 395, 492),(392, 397, 318),(393, 398, 164),(393, 394, 115),(393, 396, 167),(394, 397, 290),(394, 395, 468),(394, 398, 195),(395, 398, 227),(395, 400, 473),(396, 400, 245),(396, 398, 480),(397, 400, 240),(398, 400, 100),(398, 402, 278),(399, 401, 288),(399, 404, 362),(400, 402, 257),(400, 403, 311),(400, 401, 176),(401, 404, 449),(401, 402, 171),(402, 407, 263),(402, 405, 242),(402, 403, 466),(403, 407, 340),(403, 405, 434),(403, 406, 370),(404, 407, 296),(404, 409, 112),(405, 409, 271),(405, 408, 366),(405, 410, 473),(406, 408, 218),(406, 410, 231),(407, 411, 221),(407, 410, 206),(407, 412, 466),(408, 411, 436),(408, 413, 410),(408, 412, 212),(409, 411, 122),(409, 410, 335),(410, 413, 233),(410, 412, 208),(411, 414, 191),(411, 415, 446),(412, 414, 423),(412, 415, 439),(413, 415, 319),(413, 418, 112),(414, 419, 467),(414, 415, 396),(415, 418, 186),(415, 419, 425),(416, 417, 481),(416, 418, 459),(416, 419, 162),(417, 421, 221),(417, 420, 206),(418, 419, 298),(418, 421, 339),(418, 420, 232),(419, 422, 198),(419, 420, 318),(420, 422, 485),(420, 423, 469),(421, 425, 383),(421, 422, 363),(421, 426, 306),(422, 423, 167),(422, 427, 339),(422, 424, 419),(423, 427, 177),(423, 428, 364),(423, 426, 243),(424, 426, 482),(424, 427, 134),(425, 430, 432),(425, 429, 398),(425, 426, 248),(426, 429, 204),(426, 430, 155),(427, 429, 251),(427, 428, 289),(428, 431, 219),(428, 430, 216),(428, 429, 253),(429, 431, 179),(429, 432, 341),(430, 431, 338),(430, 434, 344),(431, 435, 292),(431, 434, 168),(432, 433, 487),(432, 435, 121),(433, 435, 266),(433, 438, 116),(434, 437, 106),(434, 435, 216),(435, 438, 139),(436, 439, 303),(436, 441, 401),(437, 440, 397),(437, 439, 290),(438, 443, 241),(438, 442, 248),(439, 441, 375),(439, 442, 264),(439, 440, 444),(440, 443, 102),(440, 442, 203),(441, 445, 404),(441, 443, 270),(442, 445, 488),(442, 444, 204),(443, 446, 268),(443, 445, 223),(443, 448, 135),(444, 445, 226),(445, 447, 359),(445, 449, 434),(446, 451, 123),(446, 450, 218),(447, 451, 468),(447, 452, 148),(448, 451, 115),(448, 449, 266),(448, 452, 364),(449, 453, 338),(449, 451, 131),(449, 454, 456),(450, 452, 152),(450, 454, 263),(451, 455, 365),(451, 452, 260),(451, 456, 429),(452, 455, 134),(452, 456, 366),(453, 455, 275),(454, 455, 123),(454, 456, 313),(455, 458, 306),(455, 460, 314),(455, 459, 125),(456, 459, 201),(456, 460, 223),(457, 459, 276),(458, 460, 364),(458, 462, 352),(459, 463, 437),(459, 461, 221),(460, 463, 406),(460, 464, 137),(460, 461, 283),(461, 463, 268),(461, 465, 437),(462, 463, 154),(462, 465, 205),(463, 464, 184),(463, 466, 129),(464, 467, 160),(464, 468, 254),(464, 469, 212),(465, 469, 317),(465, 466, 196),(466, 467, 494),(466, 470, 449),(467, 472, 485),(468, 471, 207),(468, 470, 496),(469, 472, 474),(469, 470, 164),(470, 475, 118),(470, 474, 387),(471, 475, 424),(471, 472, 388),(472, 474, 259),(472, 473, 224),(473, 478, 260),(473, 474, 206),(473, 475, 177),(474, 477, 349),(474, 479, 349),(474, 476, 171),(475, 477, 160),(476, 481, 185),(476, 478, 319),(477, 482, 214),(477, 478, 486),(478, 479, 102),(478, 482, 346),(479, 484, 100),(480, 482, 399),(480, 483, 491),(481, 483, 363),(482, 485, 290),(482, 487, 440),(483, 487, 308),(483, 486, 138),(484, 488, 176),(485, 488, 452),(485, 487, 232),(486, 490, 415),(487, 491, 326),(487, 489, 229),(488, 493, 132),(489, 493, 321),(489, 492, 280),(490, 492, 360),(490, 495, 448),(491, 493, 196),(491, 495, 128),(492, 494, 428),(492, 495, 373),(493, 494, 292),(493, 498, 118),(494, 498, 286),(494, 499, 375),(495, 496, 289),(495, 500, 277),(495, 498, 188),(496, 498, 240),(497, 498, 430),(497, 499, 192),(498, 499, 324))
    // エッジからグラフの隣接リスト表現を作成(双方向)
    val roadMap: mutable.Map[Int, Seq[Road]] = mutable.Map()
    edges.foreach(t => {
      putMap(t._1, Road(t._1, t._2, t._3))
      putMap(t._2, Road(t._2, t._1, t._3))
      def putMap(from: Int, road: Road) {
        roadMap.get(from) match {
          case Some(s) => roadMap += (from -> (s :+ road))
          case None => roadMap += (from -> Seq(road))
        }
      }
    })

    // その交差点への最小距離
    val minDistanceMap: mutable.Map[Int, Int] = mutable.Map()
    for (i <- 1 to crossPointNumber) minDistanceMap += (i -> Int.MaxValue)
    minDistanceMap += (1 -> 0)
    // その交差点への二番目の最小距離
    val secondMinDistanceMap: mutable.Map[Int, Int] = mutable.Map()
    for (i <- 1 to crossPointNumber) secondMinDistanceMap += (i -> Int.MaxValue)
    // ダイクストラ法における次の候補
    val nextQueue = new mutable.PriorityQueue[Next]()(new Ordering[Next]{
      def compare(x: Next, y: Next): Int = x.totalDistance.compare(y.totalDistance)
    })
    nextQueue.enqueue(Next(1,0))

    // ダイクストラ法の処理
    while (!nextQueue.isEmpty){
      val current = nextQueue.dequeue()
      // 現在の位置と合計距離が、今まで出した第二最小距離より遠い場合はもう処理しない
      if(secondMinDistanceMap(current.position) >= current.totalDistance){
        // その候補に対してそこから派生する全ての道を走査
        roadMap(current.position).foreach(road => {

          val nextDistance = current.totalDistance + road.distance
          // 今まで出した次の場所の最小距離より小さければ更新して次候補追加
          if(minDistanceMap(road.to) > nextDistance) {
            minDistanceMap += (road.to -> nextDistance)
            nextQueue.enqueue(Next(road.to, nextDistance))
          }

          // 今まで出した次の場所の最小距離より大きく、
          // 第二最小距離より小さければ更新して次候補追加
          if(secondMinDistanceMap(road.to) > nextDistance
              && minDistanceMap(road.to) < nextDistance) {
            secondMinDistanceMap += (road.to -> nextDistance)
            nextQueue.enqueue(Next(road.to, nextDistance))
          }
        })
      }
    }

    println("secondMinDistanceMap(crossPointNumber) = " + secondMinDistanceMap(crossPointNumber))
    println("minDistanceMap(crossPointNumber) = " + minDistanceMap(crossPointNumber))
  }
}