背景
USACO OCT09 9TH
描述
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。
FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇,方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。考虑这个有7个城镇的地图。城镇5是奶源,城镇4是终点(括号内的数字是道路的通过费用)。
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAc4AAAGfCAIAAABZVqW1AAAgAElEQVR4Ae2dO3IcudZuizd6KGIbHRoBNQLxd9pqVx5lis6ZwfF+hzJFT25b7RxyBKR7nY5jNBlxh8K7q0CCWVn5QOK5Aaw0yHwA+7E28BUq63X28H//344NAhCAAARSEvg/KY1jGwIQgAAE9gTOXl5eIAEBCEAAAkkJsKpNihfjEIAABPYEkFrGAQQgAIHkBJDa5IhxAAEIQACpZQxAAAIQSE4AqU2OGAcQgAAEkFrGAAQgAIHkBJDa5IhxAAEIQACpZQxAAAIQSE4AqU2OGAcQgAAEkFrGAAQgAIHkBJDa5IhxAAEIQACpZQxAAAIQSE4AqU2OGAcQgAAEkFrGAAQgAIHkBH5J7gEHPRE4OztzSZev7nShRJuWCCC1LVWzQC4jbXXUUL9eBdLDJQQiEeCrwSOB7M+MkUtHbV3GY5U3irVlX1yFQBECSG0R7BU7TSqLSY1XDJ3Q6yeA1NZfw1wZRFzGroac09dqMDSAQDgBpDacYRcWRPvyP7tHcLsYW30kWWD+9AG2nSyL650JQIDm1/p2qkgmpQkgtaUroNh/cZEdsZF4UNsREw5rIcDYraVSuePUqWva1D93VfBXLQGkttrSpQxcp87ajBFci4KdWgggtbVUKl+cynXWgqglThswOz0TQGp7rv5E7nXpF8vbiRJySiUBpFZlWQoFVZfOWkiVhm3jZ6cHAkhtD1V2yrFqwWJ561RjGpUjgNSWY6/Jc9U6a0G2kYVNh52WCCC1LVXTM5eWFIrlrecgoFtiAkhtYsDqzbeksxZ2k0nZ7NipkQC/wlBj1aLF3KokyYfKzPI2GikMQSCMAKvaMH41925VZ21NjNryWV4LhJ2CBJDagvBLum5eZy3cfjK1KbOjkAA3EBQWJXlIXakPNxOSjyccOBBAah0g0aRyAqht5QVsIXyktoUqbsqhqyWtJYPaWhTsFCGA1BbBXsxpnzprcKO2xYYdjnc7XhbraBT0rLO2zAJB9kV27Rl2IJCBAKvaDJBxoYiAiKxsRnAVhUUorRNgVdt6hd/yy7aknVMxEbi3WFT8zwZERbYEUZoAUlu6Aln8Z5AVq7BzkmoazF3NgmHsJAOWsUuOeyXwS6+Jk3c0Ao4aakTWsXG04BYNSUio7SIhLkYjwKo2Gkq1hpKqiZ9xv16JCKsKJlGOmC1OgJfFipeg1gBEobxFyiwnpbuG5E0wy5E8f/8k0X76/rzcjKsQmCPADYQ5Mo2c91bD5fzDzdr7CWZn2V3qq0ZtJyO5/3p2eZvaP/bbJ8CqtuUahwtiy3SOczNqe3xuf/T5h1yR7e7q9BpnIOBMAKl1RkXDNwIRFVw0TKy9GS78X1UwhVngPjYBpDY2UTX2IgriMKfoZlUJnKpghtjZr50AUlt7BYk/MgHUNjJQzB0IILVtDoToa0+DKZFZbeqmLZ42x2hnWSG1nRWcdN0IoLZunGjlSgCpdSVVUbtEa8+KCEQJFbWNghEjhgBSy0hwJZBUwXXqms6oXAtGO00EkFpN1YgRS1JBjBFgZTaebi4E6dnhcwyP1+eH/a/3lSVBuOUJILXla9BMBE1+evXDtwdZ20qN5O/b9uNzMzUjkVwE+GBuLtJZ/MiaS+Qgi6sjJ81/elWolmJ7BJqDagmwqq22dJoC7+HTq0ZtNVEnlpoIILU1VWs5VpZdy3zCr6K24Qy7tYDUdlt6EocABPIRQGrzsU7qqfYlbS3xs7BNOowbNo7UNlzcyKmhMgYoHCIPrD7MIbUt1LmWJWELrA85oLbNlDJbIkhtNtQtOEokMTU+VCRC0cIoIYcpAkjtFJWqztWoU1UBng0WtZ1Fw4UTAmXe8X4SBif8CeSX2lOP8jmx8+vH4xyu7l6cPlV1au3Yjvaj2uPXzreV+JDa6itZZKrHchrLTtkqtpFFWYbNe+cGQt0lZpLXXT+i74YAUttNqaMmam5TitB7W5W+sokdbwt6OnLTVk8t1EbSyFhXyzdpYBqkyi8Gv15JYYYbbzKpcCxYMARY1TISgghsXd6KHskW5FJrZ9a2WiujIi5WtSrK4BGECJaqZ99WQCejGl3VFrwH/7kuDac2lzLnXQjwfbUulGjjRMCIrFXVYZ+R/sphq5LUcGrDgrK/lQBSu5UY7ScIDHVzpKoTrTkFgf4IcK+2ypoPpa3KBJoO2ixsm06R5DYTQGo3I6MDBFYJoLariHprgNT2VnEt+TYvRs0nqGUkVRIHUltJoQZhart7oC2eAarCu6ht4QJoco/UaqoGsUAAAo0SQGorKyxLyLoKxsK2rnqlixapTccWyysEOpGhTtJcKXb3l5Ha7odAGABW2S78UFsXSm23QWprqi+6VlO1iBUCAwJI7QAGuxBIRoCFbTK0dRhGauuoU6tRdiVAXSXb6oj1zgup9UaXu6PCuwcKQ8pdlY3+UNuNwNppjtS2U0sygQAE1BJAatWWhsDaJMDCts26rmWF1K4R0nG94afqHUpPhynrmEYlo0BqS9Kv2nfD6p+hLqhtBsiqXCC1qspBMBCAQJsEkNoK6sr6sYIibQ+Rhe12ZhX3QGorLl4zoXcrOt0m3szQdU8EqXVnRct3Aiy031mE7aG2Yfyq6Y3Uai8Voqa9QsQHAQcCSK0DJJpAICUBFrYp6WqxjdRqqUTncXQuN52n38PgR2pVV1nn3QOdUakupENwqK0DpIqbILUVF4/QIQCBWgggtbVUijjbJ8DCtuEaI7UNF7ey1BAaKRgQKhu1zuEitc6osjfUeUtUZ1TZi4NDCGwjgNRu40VrCKQmwMI2NeEi9pHaIthxCoElAqjtEp06r/1SZ9gVRC1PtCejlFk0eX50ss/n6UZiHBGNiBU8DKz1ZOSVopjMhZNCAKmNPwzMxJvTi+Wr8aOJarHPB4A5hFZhm6z1XNac9yOA1Ppxm+7lIqNmWrq0nPbBWQUEHMsXWGvpLo7mdFwBBkLYQACp3QBruemmWWEnIRNpmarCq5sKLfGH1Fr6bnWnkBghCQFeFoszDPzmg5lIpxH4WTu1E/dMnqjmmMTNxc+aEPCGYPKS7n6u6VU7AaQ2QgW9p5/41qwsEdA0ZMJUWerlnZP0lW2r2np08Y6QjukIILWhbEN01vhmLoXWoFT/+69S/eH29T5JKIyQJFjzGkVqg3jLNJNpEGTi0Hk4l2LZDI8KC5bAfFEubp6keq/bj8+2x+yONBVrs5e50CgBpDZyYZ+/f5KJ9LolWuREDtnJnGQkGuHUNLiRNjGKnrtHgh5dguuAgZgEkFp/mqczUJ5Qftn9lFlx2O6ubi/PnNVWuohB/2jo2ToBRkjVFUZqY5bv84+Xh28f3ix+/tfNxe72rzS3796c8D8xgdMH1GOHj9fn0mS/OT+q7g346aZfr+OAOSpDAKn15C5TS8b9eueL387XG723cDX73oO9cgTkofVte7q52PIcplzMeC5EAKlNB/75P38+7j7+ale5q56ctHvVSoIG+R8ABIU4TZBKKpMfvj3cXe1u//39OZWHV7vVkUnMoxrzSG2qUt1/Pb9+vLpzeU06VQjYDSWw6THm/LeLTf68RdO746bwaByXAFIbl+erNXkfwuWtvA0IoU2CV6fRp/9uexKjMwuiSkQAqY0PVnT2/Hp38zR4hSy+EyyWJ3D/9ZO9X/D64PovhzfWxgichW0MilltuL22kzWkOpzNPbWU93td3l7dvXiuZ+fMFoRSMKSCrg3wtQAO1X6tjU/R1+yvlD2w+4p1LkclgNR64pwc5YE6K6FMmvUMMVK3giEVdG3gpQ4g0H5g90gDBDNOBLiB4ITJqdHz93/fSkN5z89ge3+KuW6DmbPOiBYDAtxGGMDQvsuq1qdCRhOjK2N0gz65nfQpGFVB1wZD6gCi2I9i5KTsnIhMgFXtZqBJR7YY3xxQyg5Jk10NvO1VW1m2q/BpEJcAUruN53B6xBUCY9nYlP1tYdE6DYG4JU4To+dnfBMFg9k5AkjtHJmJ80Odnbgc6ZRMbzPDEdxIRNs3YwZM+3nWnCFS61q9SZ2NNcRPje/l9vDhVLkkm2uUtItNwFQhttX9W02i28SgZgJIbWh1wqeizDoxMhmHnDfbXm6zT07xKN4nA8t2UgLIn3ie7OKmFtdaHgJdeUFqncq9LDoho3zZsg1OXBgvreqOzVThjiEfMTBb9LiW41qLmC+mhABSuz4M7MRYaOo3yl0sD52KF+MIwR1iybBvsEdxtLXoUZxipDiBX4pHoDwA94lhZ6PsrCZltNKl5akp08uqrZ+RU7OcKUJAyuc+xlYjjGtt1R0N3AmUvxnnHmv+ln5z4FQErZ3TS+FJGZvRBdfGHB5huAUlwQSiXugeN8G41sLLhwUhwA2E2WHgPV5F9cwmFswmPszO25X1Ze9sWCcXhr5OLrZ2wvxK5pZPO8ckYFF7GJUBYLpP9pVL0mDyEifbIMANhOk6mokxfc35rMwf0zaKtWW3xpedrtb1cq+Krg6/RKts2FYWHSGbopheC11WG7hnHdGUu1NaLhNgVTvBJ4MyTniNcUrmmNkkBdlimNRi4+13vORnZcpvQ8hznA8V2P8xjV2ClpZz1ly600YzAVa1mqvjH5tMWuls5q3Z32TLCMSmLkkbGw3ySCR1VMb+pD6WjVYnsaTlUG4cqR0XSJvKjOPbcmxmu7fgbnHVdduIqhpRIiOa6rq6kZJHao9AtqSzNrGh4MrJiLpgXbCzSsB9aCGRqzBrbMC92vequU+G9z717MkENpukKVs9gfcYqVQqSo1i2emxBrFzRmpficrIlnEZG69Ge6uC2w8KjeV5iymWSsay8xYX/z0JILV7cB2Ky1BwoyygPAegczckwxkVDTUSQGp71Fk7Eo3gGhWrQnBt5D3sxHp0iWWnB+bpcuxdajtcz04OJqO5QkO2yQbFT8rnxCSGM/np993u8fr8EOnX++JhJQ4glkrGspM43ZbN93KDcq6GMmNlFM5djXU+j5co0Q6lNgOZTTFXhHGUV2Dkgd1NMFGMjPLi0J1A16taBt/kQBGFNZvwkW2yTZGTEpWqeLJBiJJ4FCPZUm7PUb9SK5NWBl97FY2YkfCRbS+3mgQ3YoIVmTKFqChgQh0R6FRqRTtk7I5YcDiJZS+3CG4Tg8PUsYlU6kuiR6mdFJT6Spc34oPevq5wWeTmZf/qLYpQRjFSJP3anXYntehsyJA1gmumaxHB7VwpJtKXL5c83tp/W0bICC7Xty+pRWdjjTSjuWaOx7KJHRcCE2q7u7h5MgXZ//3xecXMlIWVLlwOJ9CR1KKzy8PFg4+Z30Zw5e+y/W6veoBdZhWuleEWliPk6ikBvtnrlAlnthGQeWs6GLW1h9us0HoLAaOVoN7CrHDbXla10VcWheum0r3MfNkEtWzpAjQu0tmv0PLbp+fOztxv1IIxc6G7WNXKzJeBlZlst+4MaqO2YE83DIxWyl+5PWu8yGeXzy/Pdnfrt2vTRYXlOQLta5AGndUQw9wIMOcTRWgEV1yIHiwHsOlqomg3xeDeOGm0I+P7H7v8++bp4dsHt/hG3d060cqHQOM3EBhJPoMiXp/Dmmv/RwohWzzDWHolYNhaHOe/Xdh9l51Rd5cutPEj0LLUytyWkeTHhV5xCUghZDvobQTBNabiRpjIWoZBOKTx9N/H3cdfHZe0iVLG7CSBLu7VTmbOyfwERBTEqV3emsP8YbTk8f7rp3/+9WAyknu1l7fyHtu1N9Ye52+UmlocU4l/1Oy6L8Nqwr0aqoI5DbtUeEZz/SZ5qZhP6S2fSR/n/vasfIfvYbvyfkksfZzLnNq/2uYNBMZNFSNXRFY2KZZsVQTsEuTgg7Kfvj+79Ahs8/mH4bh/xnC7bUEb6JnuWwg0KLUyb2XsbYFA25IEjFAc9HaD5hqNLhn3lG95Cv/X76/K93Szuz7f/3JEti2ESUjfbAlW7ag1VdKpszqjsgNXVXgSjAQmM9+GN7ejKuyJIPdvc71+dMtlorvvKW8s3h19I+2rX1OrWsaKx+DVBs2sCSUq2TzSoYv3+tS7I8xdCLQjtTIzXZZCLlBoU5xA/YL7/P1LgSVtYOFQ20CAC93bkdqFJLlUKYGh4J4ucj10QZ7T71fLZnP/voAN+KyH8z//eNrQL2pTDzJR/WNsgkAjUitzR4bXRH6cqp+AEVwjH1Jo74TkvQFfdj/frN1d3V5u+HYWV68fvj28evi5+yKdkui5QzAGl0PDcRPvjmNDHB8TaEGh9Ous2gjVBnY8So+OjNqKIsjZkPgPr1p99H4j6lFMMwf7UP3f6jpjdMtpPz5+vbbE1WPb6le1DIvehq1ZNErdZQvN/eK381ATqvv7LVH9eqkGoSC4uqVWJptZ3SggSQhZCRjBNaLgpbnP//kz+tcFyC2K9xsGsmoWIle/V/mpAtQ2+miuWKoq0lm1oaoNzH2gmxTkr3Rxf9w9fJo1wXP7w10JeS/tYbuSj2+5h/TaKcE/vyr79UoQfiMmkdochdQ5anVGtbUewyxkX7qvqttBD3cbvtV1a0yH9sPAvAzE7OQXjF+vmHE3ZKvWb/ZiEDQ0CKOlYkRWxoaxOKm5eXQ2WkqRDAkKpkwklp5mqrxXy6DxrHaL3YyIDDOTM2aTcSLb8JLcNzi/lncdOP9KwbBz5fvCZERjNSGPLqs2u21Qn9TKcJER0G3BSNydwEhwU92fdQ+odEsP6fToUjpLpf4rk61KdVZh2ApD8p4iLrlImwn78j3ayRa4LlFNhJT4lEdUHl0SJ1Gl+Vrv1VYJm6DLEbDPhIzm2sNyEZXxbFapm9L36FImN91ea7qBwKOr7rFULDqjBY7upbFpbzTXsdfWZprHqkl/a0a0DyRQjdRqHruBNaB7fgIHvX39AYikmps/NRePW9V2a3uXGHprU4fUorNxxyU8DU8juEZHehPcreq5tX3cEduANe7VNlBEUgglIDoiJozamv1Qi/SHwDGBCla1LMGOS7Z+JO9qetvy/JLgekipW0RZc4kRY8dobuqYi9s3ybqHsbW9u+UeWmqXWnR26yiUT0ONfklw9LutIF1Gupfbt9/xbV5zTabLQLgahYDq99U2IwrFEjl8CnX0nazFgokyYOeNJMpLzIpPkaR5zxNXEgUz4SnGqU3RbmocI7pGbOhd1VLRRoZY5Wnsl7hvi1zHVKobuiZBx+xo5kdA76q2uvG6UIBCuUytacN+uWAhRw2XUnMW+yZN0aaFfFOHseA65JJ72O4tQ+JprK/SVS21DBhnorDCT7b9Lwm+/Dj6amo5uywTAX7b7yrozHbAO/VJ3/YZ7DMUCEKgj1yjZalRapGDsPIe/ZKgwHz/YYAwu/S2BJoUXATU1jfFjro1TpM6WzCp/ddZ7d5/q7BgJCmG78hmkezEqYQhOmWDKRKG9R644x68e8vAkNrornFV2wZZsshPoMi6bLjCNbKbP/GIHoswjBi/WlO6pJbHyeCBIqvY9xsGctf28vb9lwTBG4x31oAR3DZ0yjELx2azyDq7oOiDuQhBjLH3+cfTP/Kq2OWrLfmlwoej18Vi+MDGMgGrQbKz3FLtVZPCavyOzdSmmTMwRfdqG5ZaJakpCSPp+C6e4zAA2TfJrmpWUiZ+xoeJLFhwbLZgoZNLWm4gULBOBlzqNM06K7UXR/sSjNlkeMvm2EtJM4ncJWbHZkqSKhiGCqmVikrBClLowTWQC1a5UsFFRiOOGRVSGzEfTEFALYEaBddFbV3aqC1KtsDKvyzGaitbsXGkgYAIk4Rhn5ubQw2BzcVglFR/nHPxKzlfeFWLzioZBy2FYaShSEbu41mCNJt0ka1ItBGdSi4NZBERyKmpwlJ7GhBnUhCQaSCTIYVlbAYSqEJwXZTUpU0gq6q7l7yBwPyveugQfEQC5oHQLgzNYUT74aaMkioMLDy1PBaKrWrR2TwFxktFBETIzCazQzZtkUtsy1GtNtCWUc54ikltziTx1RuB2ue8WsGtHWzBiVBGauWxUWpWMO2uXEO70nIPBXd5OZkzwWW1Xb6aM05tvkreq9XGgnggEEIg0UOaXZQYtbWHIaHSNz+BAqvaRCMyPzs8QiAnARFZ2WT6yJbT76kvE8bpeXNm+epcr+bPJ5Fa+SK/t+0Tv4zd/BjSmWCrE17yMqmVFVwTw1zpl6/O9Wr7fHyple9I/ev3/WiQ7elmd30+Vtu2gWrLTiakFEJbVMQTSOAwvV5XuKU0V2Io5TqQXpHuiefh8W+2djvtCyZe0HWRAT10mjn3zO5GmcphkcfUhawXLg2D72Sfl8U6KTRptkzAiKxImyRZRHBbhhspt6Sr2qM1bc8PcQVzL+g60hD1N5M598zu5rhIGOZSNs1dSHzh0lz8rZ6Pf692txOFFcKynf/5x9PLj45+b8Vmvs/+/Se+ig0eiSLbfCuW5LxjyV0IzF+PeUUPasnabBKSbDGTnLEl7vI4mvFfx+kUUvvh28NrsX/uvkgNRHPkr5yqA4lvlPK+iy+7n6+Zv9xd3V5qUFvfbOhXPQEzFGXqyZY6GfE16WXufOp4FNpProAiQJe7u93tpUBXmH+6kIZ3T2QUFkm/lN90VLdazkYgm6OtBEx7CU92Ug/CSQiTJ/2yqLpXilXtCZD+dPYVwcVv5ycwOAGB/AREZGUT1TNbogCMi5HxyZOjNj0cRpdaWcW+36SUld3lbQ8YT3N8/s+fj7uPv344vZLrjEwqGeW5vCn1wzwfFkZomC2p4A49mn1xKh5Pz3d1JvqbvT7/ePpHXhW7fKV4tds9CuiumEqy91/Prx+v7h46ekmwtxJXna+Zkkb+4k5Po6pxbVaN2gaffOHT4drqcJd2d/P08O1tTVsEQhGndmDp2cnAIYOLdDwleGM8oj5OApk8mS4vbZajr2qPEuwQ7qnOHhHJddAh+VxoW/NjFVbGjORmD0PyFCOMwBHA6PdqR/b7OpQb1efXH+9e3tezfeWvMlsz7VWGpisoAWVYGc0NDM6YGho5PTO82vx+2lVt8/iGCe7f1nZ7ddfVZzaG+bPfBAERRMnDqq059MvMaGuIBT+/OnslXNX29Qzi+fu/9++1kM8tDDa+1EznqCeqNQKij2Yzo3mtuet1sSkGXVu31S7hy2LCVMi2hcszm8woMrvzhJKxW2ogqe1nRDXtShKUC37TeQRndDjtr8WzCVe1LeIipyoJ9LyYilIwAWgYGs3dZNN0tF1Gh/Z88zuppLbbx67mRwwJjgj0M9T3cuv1kTPTy3IbHdrzbe/wsljb9SU7CEQmIEJpLJoVrj1cdmPk1bHxsqlKr6Za1VaKo4Gw+1lkNVCsqlMQ3ZRNxptsWxMxHbf2qro9Ult1+QjelUCHc9sVTVi7vdy+Ce6y5ppmYd4q7p1EaoW4YK2YCqFDAAJbCOzl9rDtl7jzi1xpYq8O97e4qrUt92prrRxxQ0AhARFQicroqdkfBWkUdvKSbWnl2J6RneUuw5Y695FanXXxjErGaO0j0jPzQt0APgneDMI5wZWrhpvdMUZMe9mfHMPLVyfDUHUSqVVVDoJJSGA0sRN6wvSBgFHMSYkc1cK0mVRYy9JedWlse+nZQWr11IJIINAggWWJHGmuS/7GoAiutezSq3ib+FJbHYLiNSAACPRAwEqkJCv7soWsT013+VsLuvhSW0vm7cXJg1x7NW0vIyOORmQDs6tLbZO82SuQIN0hkIiAmZyJjGPWnYARXPlrdtw7jlpK9yiqPTKb4hCpTUEVmxCAwBKBiM/AalHbLm4gzD3uBT6iLg0lrnVAIKJedECr9xRbllqrsHOSutqgotHBtK+oWJ2HGn2smoXt3DRXQrvNGwhSS1NOob9QAHNV/pr2SkpCGEkJmHIndYFxfwLys1ETWws/ZxL/vWlG4/xZB/f0DsC742rI6Sxb1xlcWF+178RiFctO7Ty3xr+J2/4n+3brv9i3yebWgKO0b21VG0Kc9U6UIYURCCwQ2DZDDz/Zd/X75wWD5pL+ydvUvdptVZyqnimY/J26qPdceOJ6cyOyjgk8/+fPx4ubn+tKWwGjdla1seRG/8NjBcNKd4iUWHd9bHT3/3v9ePHH/3ywJ2reaeRebSydtaWMazCuNRuk3Ult3zpqZiecWLiFZmBuSsSd2/P3T+fXH9dv0765d7f81iPr/xZuIChHnLWeOINAIwRaunmwL0k7NxDiDrCKnmNW9EgzeCdPC2/fiTvk6rImo85vkzSl43qyTd082Kcbf1VrREr+rtOM0ULKlshX5kRiwFBtQ54P/vX7y8uPfZD754bnn3ZPD98K3YdrprhOspVgXHhPOrcJa955cFdqeCQAtkuiU24046ST1Fcs47HsTCJLanzSY4STW+/DRXA5NhHIbdhd9sfWcx17S16uACf8DNFNXJZT24fHus1pT/nOxl/V5osdTxA4JrBV8ra2P/b2/kS4Rr0b5aLq8HDzoJH3eFmwda9qkz6UGeNRXEQxYms23Elneehl076EtKl9xMabJC8EXUjfiPlWaioFvRQ24+Jt8GUxXnuRISIjr9QmejezPd1cvI7ei5unmTZBpzfNDfEkiDZ1oXEUAtHJSx3FZpTY0hlJIrXRUbrn//rai0Tw8vJ0s7s+L/xKt9E7iT+R8M1ZPgAo82e+WB++PbyG9HP3RYB8vZ9vyxUItEUg1aNBnseZFS/bb66Piiv2R2e2Hoq0SJeVOLcafWufyOyb+bT/Hb9GJGkQ3gC9OyZNpy7jsRjGspOaHi+LrRM2crnejhYQgIAzAZlW4SoZbsE53tCGSW4gSFCGY2h0Qf2fv3+5fry6+9HEd1UEkVDRWVax7zcM5PnG5e3O5RubksauYJQmzU+78UD+FemsVKK9Ve3hrsHjfpDtX3tp6T3Q2ifOcnyffzz98+lMvnvUbFd3Lw88CC4j6+Gq99q2Lp2VUqa6V7s3nf5lwWUXRnRlTocsbJddOE6GKEZGvlLYHLno4dADo0eXHmPKPKgAAA5ASURBVEiG5ChIpbvIrouRTY1dDOZpU7fUCqPlcR/42kusoi4H6VfpFDb9Iqm6lwdGjy5VI8oWvIA1viY1d/lqtiC9HSW8geD91MA7mUQdmVqJwGow28wo1QAzMAarsFZVhwbt1eHJivZTvSxWCEGS117MbJTym61QariFQC8EZMadbrUnn3BVK2iEl8iT/E2H6dhFzNdeTOTy1yRiUzBn7GHS7KyX0U5qqiN3HEIAAoEE0uqgBJdBFBK5sGbtziRruTo8P6m8yxaG3R33oxt09Ntks60wt7ZvEhpJbSWQdlUr0RyvOreG59Q+hQv36TTSVulogx5dsufZUUVg0/hxHxiqciSY4gSSS22eDDfNltWQQqbTUF6HshticzVgGkAAAsoJNCK1QjmW2kbURCu7xuZQee0lj/ERMUIP73SBAAQ8COSQ2lgiuJpeuKNJFQs3ayIfyutQduXq8NJqmjSAAASqI5BDanNCMbIoHj3Ea1JnEwU/Cg/lTcTZ0awZNqOiOPalGQRcCGSS2pxD2UyYTbpplK7gTBu5Hirv6JJLUWkDAQhoI5BJaiVtkYxN8hdIyrgzRubUyiraXIPAGLy7D+OxQVprw6v2JDsQgIBmAvmkNj8FK0mnamWCsQ3yx+bucRSk5GLTGV1yt0lLPwJCHuZ+6OiVVWplmBYZrOHTo1TkkwPUpmM11zSz5yd7cXKZgKoSL4fK1RoJZJXaGgFpjnmkrSiv5mIRW+cEcksta4eQAbf8nGBBeUeXQmKgLwQg4EEgt9R6hEgXPwJDeWXB68eQXhCIRaCA1Fa6sK00bDNQhrIrZ1DeyflTdYknM+KkHgIFpFaSZ0yXHQELyju6VDZOVd6X796oCpVgFBIoI7UKQegPKd1UH8orC94RAf0DgwirIFBMalnY6hwfQ9mVCIe6M7qkM36/qGyaCzlKG9NsoY2fd3r1QKCY1ApcGbIydhm4msfZsDpGaGy0w0v2ZHU7m9TTpLypS3VACDgRgZJSmyildGZlpvX82DDS1tqVd6ti2vQR3HRTrGHLhX/G0YhXw3xjpVZa4uX3MWX7ej/IR2o33PbX37ZBK6W7EqkJ3js+013seFugY1cECkutsJYhy3jVPeaev3+6/PviYjnIOdlVWFyjs8vpOF5l9DqColl5qaUGygk8f/9y/fHu5x8bwhzKrhEjUTezbbCSpqmEISFFtI3aRoTZsCkVUstg1TvCjND++BwSodTXbm+SW0Z5o+uswSLZieUQRPRtnoCWl8XMYJW/yokXiTORQDigvv96LivaFxHaZ4fWLk1GJR4p1Oiqi0H3NkkxFhkY7rnTsjgBLVIrIBisxUfDKID7r5e3VwehHV2IdzjS1qHyji4F+kyqsyY2BnBgjdrurkhq2wZdX3YZhPYEylBeh7IrDYeXTvpxAgLaCai4V2shmXWBPSy+Y97iJHP+7OzT91hPoYtn5RbA93/f7na3l4fk5c/59aM5zAZCBsNwewtk/98tg/dW0kVMvR8n2xMvHuElCwfDigjokloBo2ewyluc/vr9dbI/3eyuz19FJnOE2WRiNCq/Pbzmbv493cibveRuwsvDtw+jlnkOh9EIk+GWJwC8QCCEgDqpDUkmbt8P3x7sC+8f/uePi93jf5/iesCaJ4Gh7Mr+UHZlf2RUzkib0cl0hyaedPaxXCkBjVLLYK10MJUKWwbMcBsq70pIgztExx+FW+nHZQhsJZD1AX9TcJkXI4uxyb2Ew5ue3la5W2Pb2t4G493RWuh8RwAaAqLFIxQis4c3WLwVdXQ54JCqBcBrtqvGVa2BLXPDzpNC+EVhJQTZzv/84+kl/pQslFZnbs2Cd5z06/srkhRVwdAdp8txcQJ6pVbQlB6ycrfWzNOXn7svorj221ZKB1Z82FQfwP1ftxc3/wr6DFz1DEggKwHVUpuVxKIzEd27q93tX8NvtlrswEXVBERpdx9/3b09a+nwvXyqy9NkcNqltuf1o6yjJf0mh52GpG4vv+x+mmctw/fyaQiNGBokoF1qBXkhtZVXTewNg93+awRvd1e/84yziTnw/M/fu93Fzc+3twh/+Pbz5uLx+n950tJEeXUmUccHc43a5l3iff7x9I+8Knb5Wjd59/7DUGhLhKRzCFUY1YdfP0rUv5b5LEaFvAg5AoEKVrUmywJr2/dXxcR5kpeqIxQQEz4Ezn+72P39z+ij1he/nfvYog8EXAjUdDdQ271L93jcW9qaeXSxfdmxBGYxHr2r9ujA9g3ZmfUbYpS+NROo4waCIcxz9ppHmrLYP/94efrt0/nbJxzk/hDPW5SVqLFwalrVGvR61gvukbi3tMPLo4vty86QQH6S+T0O82VfJ4Fq7tVafAVu2lrfxzt6IjmOiyMIQEAdgfqkVhA2r3Esi9RNFAKCQBiBKqVWUm5ebcPKSu93ApmHCg+T7+jZGxCoVWolhcxTaACNXQhAAALbCFQstdsSTdMauU/DNbLVbGViSRu5cg2Zq1tqs02hnBVnuuakjS8I5CFQt9QKoybVNk/tu/KSYZzwGNnViNqabPVSKwlnmEVbsdJeIYGk4wSdVVhxVSG1ILUCNOksUlUwggkhkGicoLMhRemkbyNSK9VKNItWx0Fcv0zaVeCBDeLWS4KhZIEV6aR7O1IrBYs+izoZBL2lGXGcoLO9DR7vfGv6uhnvJOkIgREBq7ayM7rkeCgiKy29uzt6oVkzBFqTWjOFmADNDNB0iZhB4qGYHl3SZYHlWgjU981eLmTzP61b9rh81Wbk2My2ZycWASFvTC08SLu0iRUPdtoj0Nqq1k4YZKu9wZouI6uwVk9Pfdk2p5c4A4FVAm1KraQtEwO1XS0/DUYE0NMREA5jEWjqHQgjKEZtRyc5hAAEIJCfQMtSKzQrUlvW4PlHPx4hkI1A41IrHPOobR4v2YYFjiAAgbgE2pda4YUOxh00WIMABLYS6EJqBQpqu3Vk0B4CEIhIoBepjYgshSlu1Kagik0I6CHQkdSmXtimtq9n0BAJBCCwlUBHUitoUMOt44P2EIBAFAJ9Sa0gU6i23D2IMpQxAgHNBLqTWimGQrXVPESIDQIQCCfQo9QKNdQ2fOhgAQIQcCfQqdQKoBRqm8Kmey1pCQEIqCXQr9RKSTQoIzdq1c4NAoNARAJdS61w1KC2EcuJKQhAQCeB3qVWqoLa6hyaRAWBlgggtftqorYtjWlygYBCAkjta1Fiqe0mO9yoVTglCAkCKQggte9UN6nkezf2IAABCKwRQGrXCHEdAhCAQDABpPYIIQvbIxwcQAACkQggtWOQ4WrraIEbtWP0HEOgXQJI7URtHbVyoienIAABCEwRQGqnqPD2r2kqnIUABDwJILWz4FjbzqLhAgQgsJEAUrsELJ3acqN2iTvXINAcAaR2paR+auvXayUULkMAAtUSQGrXS4durjOiBQQgsEgAqV3E83YRtX0jwX8IQMCHAFLrSi2i2nKj1hU67SDQCgGkdkMlN6ntpsYbgqApBCBQIQGkdlvRENBtvGgNAQgcCCC1mwcCarsZGR0g0D0BpNZnCISoLTdqfYjTBwKVE0BqPQsYoraeLukGAQhUSwCp9S/dqtquNvD3TU8IQKAqAkhtVeUiWAhAoE4CSG1Q3bauW7lRG4SbzhColgBSG1q6rWob6o/+EIBAhQSQ2ghFW1DbhUsRHGMCAhCohABSG6dQSGocjliBQKMEkNpohV1VW27URmONIQjURuBMBKK2mFXHO9JTOZwMF+yTWDgJgVYJILXxKzuU1zlJtW3mGsQPC4sQgEA5Ar+Uc92y51UBtQ1Gq+CWoZAbBDomwKo2ZvHNWtXKqKNpv16OxmkGAQhoIIDURqtC4Po0sHu0NDAEAQgkIMA7EOJADRdKWQub5W2cgLACAQhoIoDURqhGuM6aIFDbCMXABARUEkBqk5bl/qvI8NnX+6ROMA4BCKgngNSGlmh+Sfv8/dPl3xcXmxywsN2Ei8YQqIUAUhtUqXmd3T1//3L98e7nH5vto7abkdEBAuoJILVpSmSE9sfnNNaxCgEIVEaAjzCkKNj913NZ0b6I0D6nMI9NCECgNgJIrX/F5u4e3H+9vL06CK2vbXMPQf76GqAfBCCgiwBSG7se4UIbOyLsQQACxQnwaTH/Ekyuar9/Ort+nLB5cfP08O3DxIWZU5PGZ9pyGgIQ0E4AqfWvkIsayhu+DrdtN79A5mLcP3R6QgACeQnwDoS8vPEGAQh0SQCp7bLsJA0BCOQlwA0Ef95Jn+MnNe6fMz0hAAEvAqxqvbDRCQIQgMAWAkjtFlrHbdN9gpYl7TFpjiBQPQGktvoSkgAEIKCfAFKrv0ZECAEIVE8AqQ0qYYp7CNw9CCoJnSGgkgBSG1qWuGqLzobWg/4QUEkAqVVZFoKCAATaIoDURqhnrIUtS9oIxcAEBFQSQGrjlCVcbdHZOJXACgRUEuDTYjHLInIp5kR2Nxn167XJBY0hAIGyBJDa+Pw3rU83NY4fKxYhAIEsBJDaJJjNQlVMz61wVxskCQujEIBAIQJIbVrwVlJHbuYkeNSMQwhAoA0CSG0bdSQLCEBANQHegaC6PAQHAQi0QQCpbaOOZAEBCKgmgNSqLg/BQQACbRBAatuoI1lAAAKqCSC1qstDcBCAQBsEkNo26kgWEICAagJIreryEBwEINAGAaS2jTqSBQQgoJoAUqu6PAQHAQi0QQCpbaOOZAEBCKgmgNSqLg/BQQACbRBAatuoI1lAAAKqCSC1qstDcBCAQBsEkNo26kgWEICAagJIreryEBwEINAGAaS2jTqSBQQgoJoAUqu6PAQHAQi0QQCpbaOOZAEBCKgmgNSqLg/BQQACbRBAatuoI1lAAAKqCfx/DWe3i8dKGxcAAAAASUVORK5CYII=" alt="" />
经过路线5-6-3-4总共需要花费3 (5->6) + 4 (6->3) + 3 (3->4) = 10的费用。
给定一个地图,包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs,终点Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。
输入格式
* 第一行: 4个由空格隔开的整数: T, C, Ts, Te
* 第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci
输出格式
* 第一行: 一个单独的整数表示Ts到Te的最短路的长度。(不是费用麼?怎麼突然变直白了
——译者注)数据保证至少存在一条道路。
测试样例1
输入
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出
7
备注
5->6->1->4 (3 + 1 + 3)
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
int to,cost;
};
struct city{
int num,dist;
};
struct cmp{
bool operator ()(city a,city b){
return a.dist > b.dist;//最小值优先
}
};
vector<edge> G[];//G[i]属于vector类型 存城市i所有的边
priority_queue<city,vector<city>,cmp> que;//存城市 int d[],C,T,rs,rt; void init_(){
scanf("%d%d%d%d",&T,&C,&rs,&rt);//城市T 道路C 源点rs 汇点rt
for(int i = ;i <= C;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c); edge x;
x.to = b;
x.cost = c; G[a].push_back(x);//存边 x.to = a; G[b].push_back(x);
}
fill(d,d + T + ,INF);
} void dijkstra(int s){
d[s] = ;
city x;x.dist = ;x.num = s;
que.push(x); while(!que.empty()){//如果还有城市
x = que.top();que.pop();
int v = x.num; if(d[v]<x.dist) continue;//这句话不写也可以,不是很懂什么意思,不写还快了30ms,QAQ? for(int i = ;i < G[v].size();++i){
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost; city c1;c1.dist = d[e.to];c1.num = e.to; que.push(c1);
}
}
}
} int main(){
// freopen("01.txt","r",stdin);
init_();
dijkstra(rs);
printf("%d\n",d[rt]);
return ;
}以上由《挑战程序设计竞赛》P102 的代码改编(略长)
以下是hzwer黄学长的代码:http://hzwer.com/8162.html
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long
using namespace std;
int T,C,Ts,Te;
int dis[];
bool vis[];
vector<int>e[],c[];
priority_queue<pa,vector<pa>,greater<pa> >q;
void dijkstra()
{
memset(dis,/,sizeof(dis));
q.push(make_pair(,Ts));dis[Ts]=;
while(!q.empty())
{
int now=q.top().second;q.pop();
if(vis[now])continue;vis[now]=;
for(int i=;i<e[now].size();i++)
if(dis[now]+c[now][i]<dis[e[now][i]])
{
dis[e[now][i]]=dis[now]+c[now][i];
q.push(make_pair(dis[e[now][i]],e[now][i]));
}
}
}
int main()
{
scanf("%d%d%d%d",&T,&C,&Ts,&Te);
for(int i=;i<=C;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].push_back(v);
e[v].push_back(u);
c[u].push_back(w);
c[v].push_back(w);
}
dijkstra();
printf("%d\n",dis[Te]);
return ;
}黄学长原话:
求Ts到Te的最短路,随便选种算法写都可以
这里给出的是堆优化的dijkstra