背景
USACO OCT09 9TH
描述
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。
FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇,方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等)。考虑这个有7个城镇的地图。城镇5是奶源,城镇4是终点(括号内的数字是道路的通过费用)。
[1]----1---[3]-
/ \
[3]---6---[4]---3--[3]--4
/ / /|
5 --[3]-- --[2]- |
\ / / |
[5]---7---[2]--2---[3]---
| /
[1]------
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
输入
输出
备注
5->6->1->4 (3 + 1 + 3)
#include<iostream>
#include<vector>
#define mx 10000
#define maxint 100000000
using namespace std;
struct edge{
int v;
int w;
};
int n,p,ts,te,j[mx],d[mx];
vector<edge> g[mx];
void spfa(){
for(int i = ;i <= n;i++){
d[i] = maxint;
j[i] = ;
}
int u = ,t = ,now,q[mx];
q[u] = ts;
j[ts] = ;
d[ts] = ;
while(u != t){
now = q[u];
j[now] = ;
if(g[now].size() > ){
for(int i = ;i < g[now].size();i++){
if(d[g[now][i].v] > d[now] + g[now][i].w){
d[g[now][i].v] = d[now] + g[now][i].w;
if(!j[g[now][i].v]){
q[t++] = g[now][i].v;
j[g[now][i].v] = ;
} }
}
}
u++;
j[now] = ; }
}
int main(){
cin>>n>>p>>ts>>te;
int u,v,w;
edge tmp;
for(int i = ;i <= p;i++){
cin>>u>>v>>w;
tmp.v = v;
tmp.w = w;
g[u].push_back(tmp);
tmp.v = u;
tmp.w = w;
g[v].push_back(tmp);
}
spfa();
cout<<d[te]<<endl;
return ;
}