再看最短路算法 1 —— 单源最短路_.NET_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > .NET > 再看最短路算法 1 —— 单源最短路

再看最短路算法 1 —— 单源最短路

 2015/2/23 2:50:26  HansBug  程序员俱乐部  我要评论(0)
  • 摘要:学了多年的算法,最短路问题相当之常见————好久没写过最短路的问题了,直到昨天闲的无聊来了一题——BZOJ3402(HansBug:额才发现我弱到只能刷水的地步了TT)一看这不是明显的单源最短路么呵呵。。。于是直接上来来了个dijkstra,而且用的是邻接表存储图——Submit之后,结果却是——我立刻被雷到了QAQ。。。于是立刻改写spfa,结果—&mdash
  • 标签:算法

学了多年的算法,最短路问题相当之常见————

好久没写过最短路的问题了,直到昨天闲的无聊来了一题——BZOJ3402(HansBug:额才发现我弱到只能刷水的地步了TT)

一看这不是明显的单源最短路么呵呵。。。于是直接上来来了个dijkstra,而且用的是邻接表存储图——

Submit之后,结果却是——

TenlPwhKU5EjTr2/JW784iZb53hfs6aXTPX1e+ajNwn+fBTltncj6Ph8ClspHYMxmusdmWkUQS1vq0tKM+i327Rr7tm6md+TDekPqpZ2UfXssPYS528fV6Ph4hXrCLYMJa7mTL9kWZ8k8lwIT8tQ19mzdvk9FpKG0i2WRJuOFSqmcHpeXw3WNvhttRXxb0KndJlOWD/cct0W6OzEZ7lKAuJhCx92KbDf2pB9eP7VoBNtGhfX686/lWwbLA4TWBkJrZL0OV3HQluLN++hPL0P601iOEX7rCL+f+8JvZj4oRG06+H6CQvQAhaiGQrR9MdBYKVkIMEaarMWNzmOP80jiTsbH0mbfr34acB51aTaKKX2YznkMGZ+v330Yq9EnrBPsJTPryRhsw8tUP53wO/VmQ4qhQTTqNeF/GtJ5jGySycuECsvT/jxpEuo/6jXQK+uOb3rj7Qfolfy/G519edJMZa3zGoW17uQw5jUKawOFNZxzeI9VrqtSr7FPpO2xXgm5+mcu/itr8K3+9ytLeg5aB3KzuStfdupysDWWQftQ9irsr30WcZ8ZG7Ar7jU2pdnWybIhoy5p9ztSfNaV6q7SJAM2zj1pbDalrRN6YyTd+oHsd4ryrFsVl4Q0rYOb0tz9Ujp8tzXmncM9qUhT+uy8URKOido6lML7D2UPBTNCeo57Ui8UpVvqSFs3oZn5rP7AuMgarjLpGSdblZQ7fAty9kvG4itCfOpFW0mXay18jAxEmIpSeAJJWXBTU5i+stlKxpopJwUE8a/fi5KeY/qoQN+Uu/QVgvKI3wf7/P+c//1NVYXpOjsKSwfrwmma4jPKnoeIWjgI65KhryWtOhF3GSTcEA3u9ftxDTK745X07H1xqglmv7F6KS4D79VDYTVqNO5KZbskw0ZPWqVt2UDwrh/cRq55Jr2KvwjmSaNyVvGmdA6/4/fUsaXX1rPIR1mkZtb3q4Hy1aiF65/b8gs20y/SSM+UNGPmdKHYlVKn7QwOxhAth56wnjgeXHoYv6/jpPjVQGohtUxbBkcc4JZV9uEwVof3yjxJpOfoSMrFoVS7h7J9TuOEldQBLgn88XFLDgvvy8O92KGRP/86u498fXYoR9Wi1DYb0uUQYdowwNN/7z88kU9CpKcSIbsIv4HerAJyHQG5g/DbRfhNNjDwSU8Uopdh6xMUoiYKUQ2F6BiFKJV8vSQsX7liUX7qKD8THkKSuJMhe/yu1LdbUc5jqy2DRiHW/zM4D8DtVa9JcfOZDOdUmrwxuC2tCL+zJe1BQwoMwHGfPeLgdE9hU5nBy4R6OU/786RJGDhenfrolU30yk2fb+qiVx5N9Mo8aaay9uvTR2FtorBu+vOxi8J6FCisgxa6cRPd+AjdmFnGHltij91sHcNDpM+67P6Zh/9aj9m0oqRnXxq7b7EAP2dy+iyFkpMFBOuyTzYijFe36fROjxOsYJnWE4mfyb48ke+ZvGQg25VN6egJ9iQJgv7PYECefC8NnV39huy+RV7POa2cFNWSws2OlMPCH9JIu3oo9zsDuXFyMkV6OpK2cxg9uWagFm6ygT3vTibFegybxbZiJQWeGUIch7Cyj263CoZqi+2J5Nx+85vfyM9//vOlF+XGwUDkBQJ/sIwzheTmEaQmPFFEncZSs84Ub5D+BGI0bCV8hPFBFbKzTz8Fj+ZdxMBuwO8N3mEpcSToZM7rBp5Q/tIbvbYFGOmZ2rVGeqaY9a/tZFjJhg1hVV5nEX3GQhmc86iF0c8w83s25FCYWudJw8op1Wtl2XrWl4ArjTf4TPJRFqmZ9f1Kor6KlRpLn3FwwGZ6wmaaTHqmpfGUJiW8w0YAg1ZBbmIg8FwJsXCTfQWvMThh346ROqsIzZLqNEvmdTIPP6gNq2M9l0B66lqx1z9EzmKlMNJzASNl5KzfDu93ZHBjen64NRRy6QlCrKqu7vH14K2j6bXXEUt68o++WpmQnoEeHdatPeF3C+G7hfCdzKGkkJ6uCuwZKETZ1n0LgMiymImA1xcb9EU9ZpH9OvrSM2+uOs6jL7UXLQhLPztk0uLr/B8i8CSD83BGZRx2dssvZhJv0xX2+J1+7YW0TivgLIlbRSX6tjweZwOCvR6yF3V1ZOzPkDPytD9Pmuk6j+SofB290sfQT9DDw6U4gixm/8TsLkeahJxRWK+jsIblMDcfUVjb/lzXcm6zMbwIHSy4Pfaogm4cN84LysjRP3n5rzWad1eW9AyE86cI58lm1B4BWtp6yinEDEPrXJ3uLfhV+aW0W3vSvX4bg5uwkBcjZNdogFxEU+YmPWOuyUQSwC0PEgyyy63hvoD2JVZ7bT7DEyTRxRlLdefSHLg3R9yKMkhPIhxMSLW4K46rghJo1CNMxml5WMYLHteEUIBwQ3B5P8E1+yIwn6eM3/72t/LTn/50nlcWlpbpKW8pjjHSUz8/GIi0YELfDePM2GDaC/ulhPdLZEOUeUGZT/codspGx/iYxXTeDNLTTQ5KcacGocna4X+Na6A+fjU6Q1nqIEbBrTtYvzAI9JQzeOKxEAhLgk9leiyEpIZlWh76C0Hgmu4IS36esLAQJsXFTwjqtgU7X6EN6uL59gcMTgapi5ESyoPT9Yhf4ydzxO3IZenJpEAQjZqi85maUG+HzNOHTAiNI6GLoy6gD2hLg58A3jzY5kkzWfRwfb7zIXVjgv4leCTGMlnMyLNczo7ASAVwrAsC0jMpp6k07nD3WOoRRSv85hnlozipGZj2F/05475nA/iCOYabHP6e0+P47FC8Om+yme6xmdbZTPfZTBNJz7Q0ru9jBgIzkOvjsnuAItfa2mffziA9db0bsWbtsCkT5sr17we6xtPvLdbfurpVagwcTkmda4j/zBTsVqNbZ207U2diWfKu7qKzZFltMktug+W+8Tkw8i+emdLgnSDMF96uhOJiS/O/J0IBrqVsv4HqlEB69rDU6hYGntv0nKRn1rYwkam3Pbf6yfPJ+hobuAMm+uiX7Zbsda+jP0TnR4/5cHvoGfQEnKcCr7ppuxQjMdUKl/A5e3hIdvbj7u0JcyBzHmeQnihEEdJmNaaZ1cIh4BuDwYWola4jyzpleQ4pzvTyH2+PPqoE3hpZnIdmqwZkjLGwwVgexIOxFnsvk8Rz5e3LViRUQ54Co+1PfiMjjV/2BmVH9crQIXGeNLpW6zyWwGLaLzdO8Lq8CA2EwppmRNtv7KIb1yakp1s/8H6ehBTK0z+5+K88GF+dNCtKenKG0CrKXnPHN39Wa15c2dHJAvf2YOL+WjfqSk3axH3YYCevsJN7MT0DQfvXRJAjzmetLY+/2WCzJx4Kyt1pTE/SFfekueObevsu8VH39rGMhmPZ3NJ8cQNiF46QnpPJ+EIKvQp1+Fy+HmfFBr06g2TZNZ2X9FTX5Bq6zhFCm1r/BS7nm4+QhZGHAx7lxj2MfZGHsUT3SEjSPxnAmyAxODINjuIZ/IWG5NA8SritH0CUOmuVFCFO0zHcpKLv+ZJHHtJTY08WKTuoD5EYZF9jOsVcs5eN9Vny/+GHH+S11147y6vnekexLh/A1YC1WnVOHj7f4/MagjqRK6Lkst9vHBhGratncHBBvhhqy13GwveMjVOh8lxNeIVfnpP0DE9WDeZ1n/ffoZOVONT4Azqxq8z2Yzpcl+GAACmgFBOWxE1YXL3w62Gys1Hkfc5EeuKa/vbHuJkzibdGXvkNyt+l3LYSh3ymSngXxbzHT5j01GB5y7b0dOw9C06w2OkCVdFFj4nkFkwWvh0Ge73rxX/ghBq/Gn7QXnWh0gVU40bMwjYP/rgDCV4Uk0UWtz1iw2B5cgUWvbzjZ43SjYdHUiseynG5h+XedmLLktI4ErQ6kge7A+lqrDnib93jNLEexHk7q3wUJj2D8UYYoklcGfc9QebufeaNX513OhcJX6RePraI5xmcWN2wmR6zmTbZTK9xUjtNeqanmVh5vSiw7HqxBsccApWIxTYV09MRp8fs2032bRS/PKTnL26IfOavU7j0yR5r78Y7rLesJRoALljrvkQYUBO1TMEuDybLTzNr23FNoMnBuVCWvJvZZKZFmWV+xHLspgnN67ONvsXPU5b6Pb7H21W2gLShW2nw/V+KPHoBzPqCv52fxuVUa62W7MJeOqtDX+7KE3s/z7YQkannyHv5Pbe8EsajoYw3t1z/OGIkifQcxazfglibEbdztTjbkdrOkfRKx1jHZZOeI4Tf6wi/TxB+J1akkabOcG/3FaJyoBAtDyLL+UwIeJaVncpz6bKvzyLP70/GUQbn4RYJtRg9kl3O93sufij3mHAoVa8fOp069WHxu3Z7ODXWHGlHDO9Ui2FXXkcqc3vORtufXK+MNM7KtIklbMxr17XF3zMlRxqVvxPmVROFVfvm9EngmULfanzP8kEN3ZjD5uQJm7N/8vBfZxp0K/vSypKeqoh1UWL3/+YrH7x35OMnHTrYm01u4rbflvcKVU4oNV7nWIZHNSm+25XiU9zVuWhIycn22+9JoYoAhoC0MSYGSq0o73aL8hSheOLyTgyFanFfTov6WJ6g0IaNimYORjch7svwnQdSIoC7I101OCyMDbWTHkp8eDiv7Gi4pIqlBXUPV2diEDXwXJMPY6RWxCjEF9A+C6fhPTWA2vNjNrr0CIIYpyQ/vqCVFJj9BjJ3q4WM7XdqJunp53Xwa0/4DB4OauQj8jCjp+ku0NO0DriN+N1GOA9vonj5INR5Ma+mlAcf66l7Z/wxkRZiUnXqPXgewtlZTM+FrAMzAE+y9PxlcNpA4UrKXX8XC65Q/AFHFEIoBqa6OghUQwvHMJA+A4WTizqa2ow4N5HmnZX0nGiD5Oa0zo+iMTpdvtTHmSjHBuV5SM/Ui4xiRKLDhwWmzc+b4PaIugTxFjnpJ0ASk4ifpCcPtplpyPjwOv0R6lctS8t+n/3RFr2FzLLFZKLxsg6l2TuWrzYP/Tjq8ZzT07hLjLA++uyIWFfuBPEY2adwKvucVT4KNvXvWegPGTcbbATuVNN/3PeUh5veaTC5M6wBiwHxSuaiLrN7bKYufn1YgQspZ7PSeIrqUN55UJK6b0zgKWSQzsSKbYfDUx3ssW97cT6TSJ0pANXSs/3L0Bqv7B1ryjAc1zhgxPIKdqvRTakxPdk2SwxrdQhwMeMH2fJulizreGG2ITxXE/WQRHf6ONEYJz3VWot53wncLWfIyw7xwEKTLsyzLbyKpGd4ZCbND2fow90UUYtKyJEtYvFWTmNtukuQOCA+0nsrcL3NJD0RfqsIv12E38yYnikK0YcoRI1AIVqNKWa18BEYMJlucuj9yL8PJWppGMCUbsmbaOjFa94lOQP5+MuO1A62OGP0YsxO8SvxnnD7jIrLUS/d2aSn56pd2XiUcNfK7K6Otz8pdWYaJ8MQRzMe73qK9MxIk0J6tlFYoxdjp5GefL5XRTf+Ct34M3TjdII5d//MxX9d/Wm1oqSnF4C5go3mkd+pw6NqiNDc8ISmBuRkOL4J/eFiH3D6+F2HILnMrMbHT/x4C0FneZtEr+EPMj8grNSPOAXV27KyJm7CYPSF+jEs2yTwrBbnPseq9CkmypA39iQjMK+lp+YCfy099JtjDvh7HfR3uPGTQLDyBTTCtp6eWsaEuCHv7N6F6MLjsgyBVoCM3AhXLy70+d9pufDm8jcsXoHenkV6bvgcTvz2yrSbx22cnCLg+CQEdu4mc5a1ztiDvguM1hZCeqJY6IVJA7ghMxBa1Oibk/SMsNFxDctbS08v/2ESlrgqdjsWwwA3HhfbADee3AvuWUnP8GQOXN4jsSyU9KQd7rMFkp65LzJicdyDAFbv9XuQBGo96x4fOyUjE/1m8mC7nQN/ilLJNrIIuw16Ou7Hooac5XNuBAa4vRXLI6mFLoyMZ5onjYw6kBtl2VHZB1N9Vbznlo8cm6Pjl3n0kL/DwZ61Ukkb71nWgHOjdkUz0Jud2UwPg75OIj0z0niK6lg+C8eCc8s1n3OhZxB+SpXKPazJgstBc5Oe8fVOiVBcA0/X93kFu9Xoq7SDfmw05BA5xF1mFHpmybtZsqxainIRMGG+Zrd9yJbRR54+Zrp1kFm/InLLxNggtiVr/5bxoJso6iny8lSJSbJ5wrZgpGeCJbRzWX+Xc94nkEsFX1ctyWHrKzkJSE9HYOoFJ/5lvr5uGr29Pdwr/mVHCL8RQ6CpjkshxQJDIhSi1AvQVmPKvZK18C6Na8j2F6cHUIsiPZMBDe5jiZN4odRzk55jxMYCfM+2fNGDVET8zPsktT/+bp40HpezCqRnUPsRthYldGNisk8u5c6DSqx/5ua/8pSx2mlWk/TE/2EL/456TJByMQw6FRccfaTWBY7cJO5BCOPT0wJuMNt665TcnKSJLt7OSgFf4+dYvZzOpVmmzkmkJ5cgvX5XdqdiTcw2UV7toXFxtZuX9HRuyAhl6v1aRDgs8KMGX+9DXIXDBEZIxgShTMPa1TEeaRMa6gQvqnvkUeMnHIYvyV3HxYfkLqxH33nGU1mkJ1bviZc1XxX9/+XLl3Ltmiobl/D4PNZYvRohptVal/BFk40vjfRMc28P+mzSkoFnRHQM8c25it0+ubAuXjLpSRwrSbI60Pp/+AQrIzo1z5M5CXMQlitJetL4wP33y7Dla6w9Uxj538/EVidiBv5V8km6oT4Jqzz9ZGkuCAEvLFCDm3zdpQeJT540Idmn0DubfDRxX+dkckDMTuoUIeoTSU8qPEWMXRB0V6oYz3ImEgtwivTMTuNZk+xOuySG8xqjMGJqWArFcFsa6al9MFOwW41Oytx2QtXMlHczmpw2TeIy0BGHygfI1CpPqxFA5U3OzQJ+OUJ6qvt0ERI15OqZk/RMc3KIbwtGeqaEfxjg3svlAy6c250PpFavyEbtTf+Smh2i0+w5MrqHqxTd6RvepLm3DwhjUpC7CL9PEX5PQ74lzZEZloB++JIhwrVacduzGggomXdQbMhWxOLe95JNiQ1bwRVy+ib2eXiMWRajPi6z3Ns5KIvGE1fC80CKjS0cB+YnPJPaH+6dNIymxeJZrut9uAC+n+ne7qeZ0729P2tO+fNujHw/6wb3aFvOy3+txtg+Ty1Wk/TMcRKwrcIWrk7ppOehDLEGahXjJw7RTl/MqQeu9BCs0nkZMzCaZ7E4Tzde7XfnIT2VcNyGcGzEbt5Ocm/PIj3DqB1DolYhvnqcirsbvmcJcTE+J4v0NEvP843P4P4W+GnHo6Q9gbFg1TcGybrISIP3K+GpFp5GeJ6vj6bfvgDSM4hVcZ6qZ2qfV5T0dHE7CRGwzaVQAzVjxmTa04I8wjIVu6zv8+ShaVJMelxAN74z9/bzjNolvptDaUmMIxevkif7eEL78GzykdvU0RK+Z+XvcyJ1m83/GWMn4GIT2RzfBVqtwM29Jn2c+BZgaWcb7+lFnQVCRbHhzkxDLHxP9I1dKBoiPQuEk3pdY68mPu+lW4glXdyWZekZL2NKsFvi1Jkj68xtx88rl7wbKzfeZA1xC5eQaump3i37yEJw0qeGHwM/HFQS6anKNuHDDrE0mByL5CQ9824LRnrmiHnr+t0z0DkmpE+TeLm65qZGwMFsVy+ycQ/Cbwvh93218MwkPL09Xy9MOo35GB50pufOMfUvJOmISX2w34pYeAYFO1duPH9mX2R01v71xokjTw+9eLKnK7+/1iccgmlp0xcZaYjDA9lvJVl4emMuPNY/CRmdzWp/0LI8aU5RwILa88lPv8iIxS07zXT391BY3cVGMYU16yKjtLADswdYqH/w9Jqf/7qQ4bvUQlaT9EwJWHvcLMibHHs6q0xiyhzc7EqZeE4u0La3kjNJtmV/1MIT6kBGxCu6yWUSLyBHT5Ng9g9rNmp57HjYenR7AjVB3QtvcgoWc1d33yct8F65FW7vjVhHuDo2uByn712OY08iAvOQnu5EGP391+g+HEZ7jx8n6POYe/s8pKe36IZu754hxAU3geO5JypCRAhXv0rudJ56Od1+4F2erBaK4VjFFtMzOhwS3bD8vt1J0WGTxo7G+6wyOMLhHjWdXgbuCG1dKXzCc+gTno4PsmeBCCyT9KSaOnmOtPOYaJMnZaLNalWm9nkVSU8lfpgAQxbKDr/Vzb0QCgWQiF0IpDzYZqZhx9X4ezvxmJ4HmOQz24z0XOBcO1tWzstlylsm6v6UnYYhxuFyDSVnWvZR674j9rwzykeRjTU8pv1QDWFSNFjAA5YI+S53XN+zwbd+b6XE9Iw0NJ4GvKvbFdk6isq4Ggf0JjGX0250XqqlZ7xnIoLdanRb5rbjVzOXvJvQpHCTdRvQSzvTYnrqNNLw2O7OPf8hOgUX26S4t1P57W5BBuFDhbykp38mkbUtGOk5TXo6q2riFAQhI1xXOV25L7WIHhwaEEnu7T7hWUX47SjhmUv4zbL0xOPSwritxOLikXlt2XnUxehre7pOSWPGjRO4lJh3rfdyMqntZAMupYvzK5Xtkmy0B+kX7PhEfb/2gvoFzIw3vlq46HkhAn3Cs70jj7rUK6EZaWBntl9zz8JoKnO1br+OXhmVczScYpG4uQPc7zeoc3aa6Vp7F0HuRPdK1tgtFNa2C984dDJWefcpB1f+oYVmEw4hFPo4KCFP/8zPf63EED9XJVaT9ORUqcN1guVQTM8RwnkJU+3dyW1VXpyHYr/sx/0cywDX99LdPpeR9DySkfgm9UJR+mU/XucYc/5KSe72SxgM+KeUBMQp7bLbT2J6jnCJL2FOvSvtYx1wcXxTTrVcbARiZ7T8oL6jnjSISF4nIvlxEOz7XF21vi/PQ3oGd5WUAhIMIapF972Pi7pwi5wL++XzLbNITyUla6y3R5BgW9rH5KMXv+qFy45HSRHigpieDLsJ36IXSr/Jz5cIlsRzZhxCbvL9VyxEgW7vSLf+6e3tk4uM8dyz28K9sR1c0FvEO1kvv9Y+0b7FEGESw3NqNoLrJHSi/+UYnAv0ZYn+0HWAOM0IAXAwAemMy7zuHUcq6Psk6PrOrstq2ZJJT7Vk3GWiltuxwaITEC0vlyAPNpna5zJITxYIwqHoqbHsMhg3clY2yfIpqXu5yMAz3QGjbZ08DHINjOuu6qWsqdvbqYOaOh/SVg2Wq6bpWdjmwT8IyEuge7cw2u3tlzUZk8sN4jnh/tYiUFb4osdJnKgcadzFGdwSXO20/UscPdmnXehwGOy7WZ5FPoqfJgaXmQWXcgXu7x88IvYJzI1u2lykwI0czGvmgD3zIXAW0pMSBlgN7RFvrdWpMc1R/ZysDjHWwqfoJj8AAAWoSURBVHgg5UK5pZGemYLdfJAsK3XmthMUjCyjd/PNkneJ9jVblvXPC8K3tw9VVtX3yJ+Qu972wGf+HaxcREUY3RNEag0rxN/h29s30I1au8zxsHKUIi8n4ZdnW4iTnkEI7xryXN7tcll9dxH5Js4PF9OT0G7Beo1gW0ew7XABUS/NqmaK9ERvZk2+jfD7lEGYj/DUFmfE9EQhioaIuwiUrIwpBDQG803c4bgEtJMa/NLjV+qbTS7C4RJoeJH2IXeobEHeERZqWhpN4zzUqKsp24/ahMNR+cHjV8qjSublzUrg79Y3pckttUUORQdcrLlX2YLkazjOxVmjumbAz6gMm/fJ0/48aRLKGyNHFw666JXIOVzYOCIs4sE+hnchojhPmqmsUVjrKKxdFNY283jTn9ddFNbgjhgv7mhHik+O0I0hLiYXZTfTL3ZyRncZ/TM3/5W3I1Y33YqSnt4i221Updr4XL7+VuSNtx9IpeHfjD7BcyTH7ZpUam15/M2JvHHnQ26QrElpJzg9ICE3ibYJ1FhrP5ZvTt6QOx/WpVErSTiJxgBqVLln/fOv5Vt5Q95+UJGGfxPldNfNMOUP53PjltyrNqVRKURijq7uULi8ms1FelLNYwS0Cjr6Yzcu4D34uzCA/Grh/aZCos+3zLT0RBBk6EgDfVzHF90lRfKpIwi60eMLcXGnrKC8CrpVeHOAb5cq9fqGDxk+bCCeIBm52wQu5hD+gfjwjA0EWcq4S2EuDqk9DgHOCqQCfkxFOtfDkqmYGmszbexoPmX68iFga58xFV0wf1cGwr1eDp72xC+csq45CwJLJj2DwVJlEv/qcb7BktQMN4BSHMLe01uCC547OLcrSolJnRSUbN6YnnrZCrewykfUe6JV5sBYSc9U3zXe1/q2qaPG/6iGLSx9ll/JoOCmLo17x553OtHK/M9EcwGN/YmYha1Osqw03OTs0uhizf4sh+R/H0LWLD1zdPjyk4zZTKuVmosRd8ImeKdUk0Yd+Si0ueVJo0RXpdJgOOmmfEc+qNXZS/ViyNAzr3yU5ELR4LRK3cD0YEP9dtswMhCuUiXm57dsGMh3Qv1zH3osH+KrU8IZSU9t4LDbYDnx+v/GrXvst4yHAmtRyrM00lNPSmcKdqvRHblJT6qbKe/maTKyJuoUOg7ThDxRp9zyX9zhH7aHNn+7KRT6bnDIoTNTyXnMTGTqgRwXsELqNKOG1CnychjtyaVIfJi1LcQjV7C8SOkj6hcYNqxGNy6tFmnzw1uLq/Ip++mNW3ekVGuw3O2kL3dx0lOJU4TfX6XUPOwiHE3ik54JCtEDFLAqClF4z1gaMJbxTASc5d5Hf5ucBvlwEg4Qa9828l7108fyrdv369JEJt1OfDOd84jLBveQAeq4pCfnE858zLpWRY//FNHwhty6U+J+jYZv0el5m6Q3I/2SpDztH+bFKAELlXPKKPEPlW9iEdV9rgwBGn6y0iS6lKuRHAprHYX1BIX1gXJHKKzhnKMyFmnAukHckiCNu8+GA8hwyMdc/TMX/3X1J+AKk55XH1xrgSEwCwF1w1b9TU/q7TEEDAFDwBAwBAwBQ8AQMAQMAUPAEDAEDAFDwBBYHAJGei4OS8vJEEhGwHdRKuAqpC70akSj7kVFyM4q39mFhzZwDAFDwBAwBAwBQ8AQMAQMAUPAEDAEDAFDwBBYLAJGei4WT8vNEEhEYADJicefHH0lQqikqHvRimP28uVLuXZNr0S3xxC4Cgjk8LXTZnBDsXNZv8wncJefWYf3zB38MvvIyjYEDAFDwBAwBAwBQ8AQMAQMgSuLgJGeV7brrOKGwMUgYKTnxeBspRgChoAhYAgYAoaAIWAIGAKGgCFgCBgChsDiEDDSc3FYWk6GgCFgCBgChoAhYAgYAoaAIWAIGAKGgCFgCBgChoAhsAII/Du2y38qX5R5KQAAAABJRU5ErkJggg==" alt="" />

我立刻被雷到了QAQ。。。于是立刻改写spfa,结果——

DBAyjTWD7GWtc8eR5rHPP6G40Cnjx78pFJFPDkOZO46Y3Fk2dPBjKJAp48ZxI3vbF48pxZMmAAKLv6Mmtwd+NosmYqo/Z4eTdyf+Rj9uRn5DS0qsGja2Lo6tXqUSAVFPDmcyqonjltevKTObwUI1k044685P/9/xvuqZRZI02P0XjzJz34MFZ74cnPWOWc1++7iQIeQJlh3PYW3gxjaJKH48lPYgju0TUxdPVq9SiQCgp48zkVVM+cNj35yRxeipEsnPrvEqD8pN8+DFJmjTi1o/HmT2rpP9Zb9+RnrHPQ6//dQAEPoMwwLnsLb4YxNMnD8eQnMQT36JoYunq1ehRIBQW8+ZwKqmdOm578ZA4vxUgW3DcowyFd+rcpmTWwNB2NN3/SlDFjpFue/IwRRnndvKspkEYAZT86D1Zi1879OPX5bCxY5cf67TXIX2Tc8HuO1aB2ax3aP7mGmQ8X4sW99Qj8cLqOiZdwcnclqhsOoftL1uOrxI43y7F4mq7I9Q60bqvEvubf4Mqs72O5rwqbX/NjoaVuMYCzP52Plh92YF/BHIOwDF4IYtfWKrQd/z3w8HPI/0kdKgqyMDmFIjUWFt6O3cDaD4DftQD3m2l1DVj/GJDdDpT8MImEVNs9ZmrywSWAfxP7kpPEvqSwqWTLT/gjYNd24NBxcD4DRa/xXz5s51DHNsrOheGyE34fqCoD1wVA8KxkJ/n2Ax0hB4Cj+4EDzcD5z5UyRWw3kCQZSzZdUyhC6dP04AnUHngWB/AcdviOoGBu+nTN0JPeE2g+1Y/8At/w9TCWLvcGsf5Xa5G96luUPBLLh17ZWCkw5ubz5SaULLmKl3srsdgwWJPe5StHxU/Ksdqgdw3gYit1qp8HcYrrq7VuppbZtjuiv1XsrMPqeXaUvYS2ogXYuORddL6yzKbQGSy4/ylMbPgCF0y6l/KB0/tYuZq88ukoP4Onyff9y3C4xW9ah/rRsb8cNfubuXc+hGx/OSq3G3Xq8Pv11N3rcIy6cJ+jTp08Oierpfl/NiABys++/o5lk1Lnpb5hfqR+uSG6zpOsMRjaoT71SB5wsBe69eIq5+w6YGcIVNGknm7Wl/V1GL81jsJ8BmgrAtoKwDOWUu5iK3CW+qBBh9NVkY7zZyR8Gj73BK0fwEaegyyfrbp1c6ALbdvKUdugnWdrUPUzHwzqzvUzaH61GAdCnJ/fWwrfhnpsLl6MqbadtmlffBuowvpXco31j2TwKfg2o+SHvA1uq0JL+28UzMMKO3EjIxE+2GMevW1+/ChwyMSxaq4TZr3CzFRn/SDuPcTN+N2UsZDD8Pt1PFfWSLzpwSUBnivruCbp8SbATRl7Eb+E1sIF6NtEnd18Fo15zoq+uNiHLx9BI9eLFrkWPIfCDVWoKF4WZS1IwQRVm0wbgLLnYC5WNy9GQ3MNVsweQE9rMfxbgdePB7F6ttLbnlY//Pun4/UGofhOQfh0DUp9IeQcP4GSHwh0kUpvyTK0TKtH7XYu0FP6cXZ3LgLtPhwOVeIRCUAqAnHosXbsfS0X9w/wm7JlqEY9DjeaD4icVAeLEdhwCNlUkg0A5eUgKvLKcWNDCLUvkbnXu9D6ai5O5p/AroL5KeOoiIUjMmZ/en1Syvrg1HA6A5RmYFQAaFtWETwLEgC7C0DKpG7clwkkUkF/MsT/n6HU8PcKKsVT91jTepBKc4Dvz/OfHtweJI8CfqCQ9RQs4iJ9GlwX+DtB8AL1gHy0hOAkLylqeUiYy3VAK5NDYLRED2Q6CW+c75NK1zj7mGmfDZ6vxOqzgO/ev8OpGR+iNd8IzaTLeDtax2HtjYP4XZEZGIixhx5AGSPB4i8+pubzdQL1hQTqPxh+kFD0rpVoPlSJJ7k+Sh1r63TseKceK9RLXeVv/XixOSgvg8MXmlBVeASrQ0Hkq+urOLis2TMfOwz62xzUflCHJy0ufmWdpYfQpz9oD2OHEwDp9D5+/ib6y3STn0HydLPvb9G+hOuQAaAcQMfulVjbvhh7Vb2791glynZORyV16sXk7eBHNdx/TyBPlQ9E1akTTdnU1C8sKIXeHRWgtLiUD/OytYq6CnihukugfunyWAGU14+gqugqSv6hGHNHaEgw0jNAus2fkbDNfu4Nr1VZi4HN7draexVHSxbjwLwm43l2VhBHf7ZSuegf6ECjLxedgROoWpvFs+oJNHI/OBvoRuNau7OqClCaL5Bo3BMsexxvzWrHr9/MTUtQww0vMkZ+VN6eLVBxCFhhJy5kJEK0KJgHy3RsG4eyqR/i5Cux6dJO+kHce4ib8bspYyE0Sp86eK6s57mSeo/Em07wXEljB1XvcVPGXh6JT20jPrXnPVS0mwDKOOasKxoOnED1Ej96t59BNXGqyQRBGwufwrGCDxF8KTaeuplnIy2TJgBlB5qffRznNnQTBNQWTAKJLyzAsWIVGCRha5eUY2rzGSLNmsYrkP7vIIDfooOLMU7zQErlem+7ojjJRzDke88CoT9h8zP840d1KFhFQPMD3gJqt/u0LihaEoL/Y/5NBUNBwLFtWzFvsC5h5pfXTAAl2902H4GPa3D0EDdrjQvSSuEMij4ZUu5HyqBYvxexcETmbDtFKdb6ElF+pMpJIvqEKArX2Z8SAJsFWnokpOW0qjSZG7eUA1ozvvcmQUmVCj0HgdUEDX/XaLKupQUk7w/QwvJ9BDX1AOXJV6ncE5hsfWmIlKLusjCtJmmROZnAZ5GwVOABITLnxWZr0X6imJFMuiZqDGOr3n6c/N8zsIvAZPOMOiw9vxiH15UjHQ0LPYBybEmW6O1Ymc+9VKq3lG5GF2aj78tyk6UDldNHn0LPnq94+aZZBSh618mXviBgQo8RqXc9i66txsOsBDY/KOfaLQ6piv7WtekrVOdr9SgH3NY8i0PwtRAqVq3DOW66faWeBWVqpb9fWsduKQ2hZxb5YQYopU5biazQJWwU+rOiVEv9t3rWEe65WYoOPoV8fE1nCXuN1tyP1eCJ4x0IJOECMLU0VGJQRtO7o+m8UufhBfjRf+DlaaoHorVvAVAKKz//x8XkOQ+yHkA5CpxymHvmFgRA/HQxwjs7lLVZPPI824GXP2nCas1LUM69JuSoQEr42Dos3Z6Fw7/V6T/v0xAo0M8LpBrLCyTABqBkk0IOFvvmuLCaGwUSJaiKsbJ/Ow1f4cUU8qLGZOn8ABqf4aW8mKsuZES2ExXzEAUUr4ezAb2+4NRD8d5JP5gT9x7iZvxuygwfBc8Pr/L8sEiloVqgY/ccnisJ/r8mwH83ZWzoc42XBBv82PUxjZ+ILxWZAMrY56yKhTnsw72tPvxoz0rDWiDpUzoHh/+FRnxu2JnEMmMGoNSIeJBEtMZ5FQZtnPUu0X07lyFtQXcCKJXFuRa/QO3eZTj38FM4b7CgVN4HqXy3GG6gqPDTJSlMYduYJNdRs6w4uZokUbZsm4oZoDS55+J7tI6jW0xFsQpsqcpUA4GtNrpjhwhEWbn5dtDFt4b/NBdfg2uNA0BZTTBbA8DM7ihyCbZwWxftbaE1YDffLye4lk/9fouFe3I68ETrQ6o37k7SbA35aQYoxd9LCTTuIFBcqrdEoGxUUx7uoSuMfs4N0opycSm46NJVyYbA8mDA7yxDDYwyU1JN11EeTvpX91UIm3+5DgtX0eKD5s/rf1WOBct5yM42mnOFLwbx1tsM03GT7g5guI/ZDPeRx3Af31WG6PQePXSXOEZ3iRvie7o/zavD5h8PuUtI8BHtOHxvEzZ+wrAjeIht1KhtcB9poRvXDY2cL6D2v/KSTMS9CDMMCS/a9vXRbcuiX+KLwc8YYuR4JVpufoaZExjuJIt71b/8T8/FOwnSOSbmMw+hjwSOMJRFPQpRiedLl7k4VCqHifObVIBSHnbredg9EbEakOQVdef1Kwcj7YJXf+nLIj0HV/KyqZxrud4zRSj1WWhZEkRB+7Mxu3jPoAXRbFoQ3aQF0eV5qgXl9oO4/X4VJtNlSYTaucVQO1cZaufrJMhBvE2ki/zIAwvDplQ2NCH79AyG3jFZUEo+X0Xz50ZLWPkdeXGU1paWoJpqGDDTbBkSIZjCu/HBD3Gb69x3GG4JdB+9vakJ1/L7MZPuqBo/B98M4g/PTMct8S1dFefRPe3eEMvTnRGrfBjYVIMeWvbK9yl6nGJQRtN5e+nO/CPqKhGXaCd9V+ib0XRZQQPqs830Fmkh8HmFv2bTw6SSv2uhrgaph7ZQNw2q7x+kl1AJdWe/dm6xACg7ds/HuWcuKa6IMQKUEV34S+rCHGvOIPAGf9Z0r4hOTV1OuJZHHs51K8OAdJk/IxE3x7lnqFxYMi/D2nfKDUYxco1tX2eah/pLpunW4I+cn37MPE79yPICwQGg3DrfCHiOhBAp+DYT5MeebCpYRSxEhE9xlhEBdjthHmLtFTJTh2zTPu/Ivpj0A11tjnuIXcvG8VuXciijtn2PCcsxgHluyoi1erc4A+gvYgVO5MPJUrqPF9O45mmGZTLskzZgo2nOanuw0ePBNFoXNJRg6AbOZw+gtBflnoM++JuzVBchzdVoyMVbm2S/pkXUITXu4z2MCVC0vU6NQalZXHaigu7aSrykKRbxcliuaBkOLVJN4lW3cKOL9wDC1wYwdbawBlBARyuAsq1Ab/EpxmZV1nH6jmoBAVBOmDAho1y8hXvuWwSmGn6mWNVpbtf3MZ5gtXCLUZWpmQQBm2mNt5A3iVIhbODvBLOEi5kEvghgHubfHuF7UcdGKmXL+Td5w2+jcIly1XS/KRLfqdiGG4BSxEosI6Cm9ecs+xMQMYhM7smjyvxRqCyVG7egdRUV6bmk9Ubh8q09/Luff3/5HeC+JlP8UpVvOTp3bvmZKhO1vKGKWEWb6HOUMSvLaLrZQblKdNzYVNJ1FMRizFXRc4wWXhdyVavJfhylNeUbk3+Lo/9FdXsSI7rIeDIEOp5YFiJQQiVt8CpO/mMuSm9WKu7WTu+vMszH/y2nOR1dp3LoOhVmmI/QSuya0IRf/43i/iQByiuz8cTsJtTSzer+m2oZEVKkSAFuhllQfs195Jd0u5jBMCTiGyqPJ0M+lH7lx+ES1Qqil1Zov6rC1L8MoWrFfKD3CGpDeTjw77y48WJQJlxex8R8vn4VvZPn4H7uW1KZdQQoRTzKdSjdOR+176iWNRKgpDuh+VAigaszqBVeJ59HAbFMbQpl+PmdWWg44ke3iLEWQwxKBZzsx0AwhEsypI8Cck3mxcAt/u0POXMwgaF35jL0DmhldEGzMkq4NMTeQLrIzyBlZHDaHGWtEgcpS4BSBaJ1w3SUJ2m1E0KRGdiO1KHyblYh/kQXuit0obuP/J1VegZ4Ohc399bhC4Zxuo/nglnb5+AGQw70TOvHnxPc/jOunVff9NF+BZjetg5zAgP4N1qQ/UEfZz52lozoi4e++yf5fawu3uIbqZvyQlUD65z0XUdd9jr1qKep4xLcq1qrXOJ3Um9aQ335IC9kF/N9BXXf+wlQblbDFsn3BCj3MsastMQbBlCKi4smPNKuAtUxAJSd1H3XUHfTdO+LvBgO0MCgT6cLG3RqF3Wny/wZidA4zj195XIdLsdcWjJLT0D1kXP2S8WDcEiH1YOL86Ma0xjPtfoGo7h48/yN0iBj8Y3dhFCZID/2sqdcMh4rVQyonGVEGHQ5YR4sItf0I8gK0MhHxrvkZTvjkVa8VizP1LZPtEuuaDqJ4x5i16Jx/NalHMpEvZhV9R5Eu7xVy2geuYZO9KP32hTcP5vzR7ZjBiijG8DZz1mLkTrQcPDaEewLFKM7cAb7bMM9jGSVG9m3aWJBKQYh/PF99Md/Wx3RX+HFEA+OvDkVj5xkoaXIebqSCW1EfMkB9B6rQhlj3+S00yKSSWwEkNi25AU8uYHJavLpXz/Ag91OHuxO+3BQjZcjKxMxmYoYk4mbpnye/l9obqFCbjnJrEBHFeEOt+K9vb6hOByqsMEcr3JkPIrpa3GTO2nSJPzrH8fH9F0yC9sFDNf3oUJLkqO65xaYACih0Gyk2668XVWVqR36MvxuPd9nqzEGZXm6AXcS4LZ8bJLkiLIzqezt2AusUEMCOAKUal3LKV9+tqk9zYw0UMMb4mRY7MXLz1Rt3I25DLjOG/UweVZLkFm/4bUWAie5KYoYTcMsEVRa55uBSAeAUsSz9FNBzvdiUMYrKmn8HS+h/n4BWmYPxZ0Mv1uMpf88BQ3/neE3ZDwBruH/hxb3DA9iAC0jo3LznmE+Buvx3t/o9gBpuVmFrDy6Ni7UAEruLy9yf9FOEDJWJN0f9WV0MSiN4KrWISpU9Y+jO5vuNU9NR2fbYqz5qsrQ9uB5umqc2u0BlEmQzFStk/EOzRFQ4iHCvy2E3nf6kb0nSGBDTaCg3sCHm/Xu2xrgybU6AlAKCzCjd8uwNmX8o0rGcxYxw/uVJBCuAMpu9M6ql+DVreYj6I6E+FFBru0f4lO6smkWdNPaivHAzsX4I10auaWk5ZOO8mMJUErrlzrGeTe6agtXt7VMlGOdHEFxBaye3GoR111jhwXv6ML68MN5GNfQzaRI85WC1KkXEZi5TUuv7h9oMUd179OEuwKgHD9+PLpvWF912llQiuR+G6nbzNXibrvQd510WekZwnjcR5nLwsq61dKl3AwKmgFKIQd75mCfFncwir4sWaJZPhIM3cxkN1maIYDKr9YX6E3E89YwC0qRJOcuASj1oms593QFOvdzvw8WD7NaHG6dJT4aDlC2FZhyKDga00RJ0jPrrygLjFmbo87RNJmDsXQjHdffWPofrWwPLyNXb52CvWr+DmcZMXucWhtaKQlyLuFFXgau52XgZHFxTsxmGL5i7pwEKF3oB4bv3Owh1lQwj9+qlGMZ7WJWH/ZPVKS/mJUAJS9vo5WxBCh1PYoCUMY+Z80jjUZDkXulGMH3u3BuWrGa+2W0JHD06kkTgFJJblONGjS8qaDxMhB3BHycogCUDTzomWJmSEWJgdh/1zIfIQKULRt44JTxAYYUIRFn6fx2dYFWk9tgK+N5SCXcaZLZWEUSmfavqsGDDVqwUVrGbM3FruBnwxPqjB6/HGsSsXAmTpyY/gBljFm8B6m0nCcIdZE3vOfbgFME//o0JUhVppoZnzASkN+k5PTymzVUBLPpXlJYzHIEDg2qpI1SJNrdx+8O0ILTUplSOaJXQCczteFSWvyZsxjaZaB2ZGoSC6R645bWAXR5OkwFW1is9vBnP3l3WI1JOSoApZqM5wploZkAd6KtJwX7Uk3XJIpQ6pu6wJvef6L1DgNaRzJ3M6N3NTN6h/8zgRYCfCIuTuNbj6PzL+nKukKN52Toubv35x+lFf1KvaJOcLSRsZMXcb9ZOUexjrxDCwe95aZI1GYuEwEoGdCcbt9l99ElpECvOCqAaWCC+DutIlgmOJc35PpDgpckJ2myN9bmsyNAqVGOSRCaSx9H+9OM3cpA+GJt7GRmZ5EAp7a9iTF8mZyQCVWqCysR+nxZDAAlXRS3LUPN1Ca1XnsXwiEmKoDUJB9vqEJEW3Z2ors4S+fKq7oJ0z3qU31IHYIp/4kxxQd4cLjsdEBImsQYG0pH+bEGSRSX/NKPyyOJlIRuvnFDE84Ni2kqxqgm1WkQ8jKURGk4ma0SHCl/A/nZrfFTApRr6QYu/jaAB5iwZ1rDFNzesA5f5/nwR8ojvYVT/gjDAOG59En/RMu+2F3KZ/Pg7mPsbL/eY4Q1RNN3nXRZYYH5BjNsn3SImd5Lz5Qu6tMXqT8fI4B4jj9HDANMAKVYP96g5WokUagLEFESwko3F7uvKSTS3WhBqReU6AClvbWXM/ikWFDGDnbYrM+a0Q/Bank5labrq9OCkI7rr1Of3bwfJIAWyKuTuISWrNdZRtwBlNbta/lDzAC4rnTMAKXbPWR4j6zGby7lpoxi2egAPqY1QOmehj30Qli/qR8v6xJSu5G1ZJRJD4CS2ZJWMHFNhS47khi8vDVqY8wNZo0LE4hcI4FIY6bTIcU7F+ceZewkDYiMUM+40HaKeui+ZEhuowZx1UyijYS3d9sOf0RXcsa/CX0wgAW+clp2LkMXA8r3BGMNIjt6rBYApVCULnw1YfQqHeWaYo1BKV1xqUA9QbeUHFozPkllrovg5BaTBaUBELRQoHrpRnOgiXEqCX71EXDMI0C1nsrhQuGpEEXhkvEM6T6+lwCpyCjvZEEJc0whlX5Rxz3KNI63upRv3GpMyUGRNZ0gsrCCzdclt7EDKO1cvDWeRehBcHIzedlN0LmBCryWnCdeern9LuV0ddvRDCgnrQu7z1uP5N6/x9G/FYnNuK6/xcOwrTu0u/e7bOj1RJYCHioxKM1goxJ7sm2eDsTUAZTGuJSmBmYLsHMKWtj3848q3w89Tn3OAOamyRDG2nx2DVCSvkpQ+QE0RJL90fW7qRxv7GnG+cHvc9+sY7zfDqz2XVLKXIji4r11mYxttPD9SvjpQvp6O2NWSs9A9wClcOG+XTofE7lv36QSPQQ6WgBaomoJagUx6AGUMc0We5DkEo7+dB12Me5j9+TnUEidt2hKFZ43BdtXwMlclDXM0WUZtutCPAClqKsfs9qamCyzDhOPf8a4lc8RrKxCX/Ey6fKdqmfRjDtS7+7qs+5BLLqfo77LJqLpslb6qaFXqg50ircPy6lTC31aXNhXU7fO1jyXDAClAKl96Nugi0PrEqAcFl9T7Yj8O/95FpQKQaIClNJNswk+i4RT0dx3q5eIbMtzorp4dzarsYaHiW2U9Vm1qu+1/TZVs9B9u2Nt/3YzMgG8lQTqMJMZmjVwMiJbNmEAFBkxZ/WIJVSdi308mou3qh8M5QmIZQ8xUsVu/PpSbsrI8lFdvDuIBQSxOqqLt1rGCcCPw8Xbfs5qI42Vhkp4xJZ8Y0IgNzKX6DLpAVC6QNjnCvPioC8KQFmMvpIHEMo3I/nGCZTQ2wSRZe3hSixIYeZCcZMrXE0+vT4p0bITd/2xAJQCHFxNQGmzKQOzlYu3E0Cp7/BFWjnu4oHpPF1KZKbnaAqXyV3YCaD0LCjjFg35YSMD851nHMrX+bMIHm/3aPEla0UgPxdJckRgeAFOCsvJZIKTov+ZqBCNjMsJ+pqWkrW0lOyLWEoOtTN4vhKrT3WgwneElpUKmGdvQTnS90q71gCl4q59LsseoKxm9vGTP7ZOByfBHSsLSrqXV/yyAI94MSgTJFxD1Y61+RwLQGlwY7JRsA1ZJumVsp5Jb8xxKvVJcnqEB4yIwWz5VNu4CqsWlNJycgoeoNvwvbPa8QXdTOk5ysfGgpIH+ixeeN/0AMqY5oGTm6m+Mmk8QGBayeIuHhGiKReBoJPlpFZLvADlUC8m0ZprZmsN7ttOczxmmf/XFMbQcloP3AKUrvRdE1fNuuwxhjOq5sWunQXlWcZHD1AXOtqicwHXQiJZAZQCkGI4Ep8+C7RLgNLOglLGpdR5UXkWlBbxX1U+K+6oykXPEJCjvJTvhiWr0ifJoRfHNvWSlAY0kWcESXLSIddCTAubRWGn+TrS+pP9ffh0JUp9TQbLSa0PbmTE2N/YAUoJdPq7ZDxFHq3Vh0kfhZUtrU2c9ANxhIu+hyh90hsEVOgSy0Qbv9YbN2WG6MAYkqo1vzH5qj7jtZsyDpJgCVDy3BDXnHWioV1fXIDMyRZotb30AChtAnlebFqJ59uLFWtHuu2ULDmBQgbDlkGc5UO3t22MA3a9SSpKNw4yMcI764xxIbkQ19Kq8cYexapRb5U5FJ+lC8EXHsExfzcahyk51pNVWmKaLDrDjH20lLGPDus38iQzViTJGTdunG0snCR3x7K5WABKedNKt99fH6Glo1abGtcmZHLxjgWgFFUZsjg7WVCKLIvMCC0gAwM4qvZJ3nqzX/JGmMpeiWr5V6DGrRTFvBiURnGwdEVSebtQU5RNEmQlOydfJdhMCwAty7r4RJQrC6vgM3/XwMk+8rExSW7d+q5nmkKUDuuIVR8UEPIqXv9v3CdmmEqo4OWpBSI25XycZOKcLebEOZFPaDUSz/uveZhr8uMeNWO4BCiv/UJN1qNW3sO9LER3WdUF3ZwkR1qAXqPngLT01B4lrmbbPO5RtMy0jkEpxv53KPIAyoSL51ibz5YA5TUC2o+tY+ILZnLVuUhLPWZTFvc7EVOSoQ6GeaYw6VTZDLz1mHbjrrh5dW3Sx6lUlN7WPCudSrDHjVJsBLEmUU9cQEuiO+1n6NI9lCRnksn1+z9QD5zVkOvFoIxxFlgClJYyYua3Ck62ZmEv17XVOp3HvgsjByi1uh/kYW7q1HfRxYy1qXqc1gO3AKUrfddikHpdtk9NCGkXg1Lory20nGRIw8gTZhidpfQqsXTxpgFJzumVOKanr1uAUiTsYQzKBeYYlIzasIUWnJ4FpcIC+8sBNd8BY2UbE+GorJNn5w68rD8XS9CjCTmqR6LhMknjOHm6ItCPWlPItCGJcLKgZAZw076RqrkXT7tO8zWeOlP1jQK8BbGgmbon9dphjwsZMX4TBfOgx4Qh7+pnUD4AAAjcSURBVIaMK019t+ES84XYJU1yox/Es4covXYcv8syRhoIq/EZPFcarQpFSMGycFANI+imjINU2ACU8c1ZZxpa4VYi3JXQ385tiOKmnyLhTg+Aksrq0ZLFjHEyFIMy/D7diGiunNXQpQq+4lNf9vE6NU7lAHro/r0x0IG842eUTMwDnFg+HzoDanzJAbqmbPXzG2Y/PaJmPxUK16p1vHHVYlD2o2M/y/BGOJK50sCMaDEog8gJHUEJE/kM0opgM7NHTt3TJYHQVD0CoPz2229tswmmql/6dmMBKME4OQVUpvI1wIoKTysBqS109wIVqveYUGXqsIyDfGdSoASA+Bav+htoLSmymgoTjEYqSWdZRyMzHdq5eGsxKLu0cix6sQl4nhkRG+iGvIIWJj1U7jbTGvMcQUlN4ZIAGV3CtSzekcyFBMiSkTU6Xj4nc+MWiWoCjMGUQ16WiBhMKm/FLZkWc9I8DivZGaSMBBjzM4/8EOtAmFa3pbSULNSSJtFtvJbtnBJKubCWjZc4I/gumXQdQTfH+KdKtu4yxlgwJK6JjErEceSFVl+lAhias3TfpivrsWKsuUxrhSJaK/SYsnwPe1+PIsblW/hoEypWMov3bTXb9o11EXBRy+K9fEEItX+9DFO1LN73UslR41J2/iMvu/rq+I0PMwenYPJN7k2/LEbPvCB25K3E/RP7cZHZjwNdjPtUzCyq3+WAvlLKhLUM4l4W76TK7libz9YWlGqconZfJL5g+KMmVPkrZRbsXWoWbBmDkpY6zYcqmUiQeldrMfxbp2MHMyuvUC+LRQD9NXum4/WGegJUWhnKKy9xI3GhDRyKHaAUF9IP7F6Gae1+XGfSwy+maJmgn2Nm7yB6fjAdUxgfc46vEt9SD/skhXqYkzCmo/xEi0G55Xodgnv9TE7JQxDduAPkgaZTSwsd6jW15kzvUYkQD0DZgfk8SE0KfIgvixdLK9p71azt3/CA/KntAdmJGyN/78RPtwClG333rJMua5HFu5dmTaXMnP0ygcK51LdEnO+DDOu6mPM3TP2pivpTOzNKFYrQOiKzt06nnsyzUeixM4bs0W4S2WhU1eKKN1BnFvqymyzeFYyhOZc6/3r+P9kC93Ci98g5mtwaooVXEAmngrzoERmZhz/K2fnAtHoml2TyWJ5528qYz2EW9Qsts/cAL5l8uThbcAS1TCY2lUliGwuf5dnH7vJItOIQg5LncGOYtOTSa6StZYz8SO8FHmCZWGyfllhsGHFcyIjhGxvMQxqJ1WNuM7EOmYRYwVfeuF6OYCP3hihMcdIP4ttD2KCb8bspY9H3QYYeDDAPSh51iwB1i/DpGp4raSSnC0XopkxUWbUBKBHHnHVFQy0HC8MAVFNe9ImkD1OnEnkf0ulJE4BSWRDP7q/Erv2Mc8RkJw8uCaBoex0CP9SDfTyotVah+udBnPrkGh5c9Qo2bq9C/iJdmetdaPt5OfaJeDlfPoTlpTXY/BM/FuozdF87gebtlWgJvocreAjZ/nJUMiOh2KyHP1FiUBJErSqrQbvoi2V/k89q4eJ9584dXL55b/Ibd9liTAAl67xIZaqabimnpFwwoDgVrSf481oqU4d/y2QqLgBKoc22/Zw3x1R6hHzN5K1uDuup4NouXZRsshJq7RUxg7Qe2Dr6U1rtUdHr5h9FkPMixrQUSp8+Q3cHb7K3MDtjN6vPY1v5VADL2JjMPJ6mT7I3bpHFspqWsCGCiWCGc0HLzfxnFxsyWjbMKiru7Qz0LnhWspNyIi4t+ITVpEV2JDcnM0oEa5JN10SMIe3rlBm0CzCZ7t0i07Xl00nLgeN18KkWjuGLQbz1dhXabv4effg+ls8sx8t/vQ6LVetLp/eDn4XQ8jb3khvq97OreFHF/UaAiHwkQNn/C9TOPIN9lw9xLWAMv3kEgX5MsFLr4FX2O7QOoTtzUKlm9sZXZxD8pyo09v1G2aOmc4/K5x6ltwrtOYLGY+WybUwoxMvZK3Hqn/8Hsj0LyoSL6libz/Yu3uKCthw1DnpXx/513Msov9SprPWlAe7Tldynd3Ofnk1LRz8qdtZFsaaLB6AkW0Wm56fzMJ4uvd1rr+LP6YY1vvldfEPQdHKI8+DhQgzurccfqDdqWb0TLgxxNJCO8mMLkgxQp95WjtoGrkWzuEb6uMa9xjVOHmYU64saXsZaPTkNdlYZ8QCUIhTPCTy4vQqTj78NmaKdevfgpipcoVV5KpPlOPHTNUDJITnqu066rGAE9dlmhlRooY58hb9mE4B8kTroanqaEOcnPwkoM4yO/l0P9acQQx5JT5SITn0J3S/UYGbL0GWE5LNTFm8WiVhj8udOZhbfRZ1M6PDLCWYXUHY20s3cLvGk0J03Ui+8ohkhmITLid5xTMmUfmIPULpwtx02P2tQ9TOClfoRXT+D5leLcYBrZN/3lsK3oR6bCfLbx2C3yeItvg1UouQlnzr/U0q2uBvPFPmRHqFbbeKt5x0cConnRkYi1LSXucELQezaSn35OOWIe4GMR/1KblRwUqk2mn4Q7x6i5ilxGH+fWxpZSJMwlNNjPCXUafwEK/WPUxnrsIJqDXYApXjtMGelTsfwDkpeFvc0NPPQuJ/HPaUS8mEaAZQJGd9dV+lfTLuF27dvp7UF5V3HFHXAwhW5keBZi7DYTNMnUzbudCOvR9d040hy+mN2305Oq14riaaAN58TTeHMrt+Tn8zir8fP5PLTo3dy6Z1prXnyk2kc9caTiRTwAMoM46rIJigAyu4bqXBkzTBixjsc1S39Sd5eV9BdRnBCuNiU8Qb7RbrYiEzg6fp4G3diOOPRNTF0TfdaPYAy3TkUX/+8+Rwf3byvFAp48pNZkuDxM7n89OidXHpnWmue/GQaR73xZCIFPIAyw7j6/f/4LW7duoWL4XsybGRjazg9BCT30b371Dug66jJxSaNh+Jt3IlhjkfXxNA13Wv1AMp051B8/fPmc3x0877yAMpMlAFvPUguVz16J5femdaaJz+ZxlFvPJlIgf8PGB1tEyS3gwAAAAAASUVORK5CYII=" alt="" />

4000ms+(估计还不止)和192ms究竟是怎样的差距啊QAQ,本人虽然早都听说过spfa的强大性,但是未曾想过差距会如此可怕,于是HansBug‘s Labo Online——

准备:1.dijkstra单源最短路径模板

 1 type
 2     point=^node;
 3     node=record
 4                g,w:longint;
 5                next:point;
 6     end;
 7 
 8 var
 9    i,j,k,l,m,n:longint;
10    a:array[0..100000] of point;
11    b,c:array[0..100000] of longint;
12    p:point;
13 procedure add(x,y,z:longint);inline;
14           var p:point;
15           begin
16                new(p);p^.g:=y;p^.w:=z;
17                p^.next:=a[x];a[x]:=p;
18           end;
19 function min(x,y:longint):longint;inline;
20          begin
21               if x<y then min:=x else min:=y;
22          end;
23 procedure dijkstra(x:longint);
24           var i,j,k,l:longint;p:point;
25           begin
26                fillchar(c,sizeof(c),0);
27                fillchar(b,sizeof(b),0);
28                c[x]:=1;
29                p:=a[x];
30                while p<>nil do
31                      begin
32                           if (b[p^.g]=0) and (c[p^.g]=0) then b[p^.g]:=p^.w else b[p^.g]:=min(b[p^.g],p^.w);
33                           p:=p^.next;
34                      end;
35 
36                for i:=1 to n-1 do
37                    begin
38                         l:=maxlongint;k:=-1;
39                         for j:=1 to n do
40                             if (c[j]=0) and (b[j]>0) and (b[j]<l) then
41                                begin
42                                     l:=b[j];k:=j;
43                                end;
44                         if k=-1 then break;
45                         c[k]:=1;p:=a[k];
46                         while p<>nil do
47                               begin
48                                    if (c[p^.g]=0) and ((b[p^.g]=0) or (b[p^.g]>(p^.w+l))) then b[p^.g]:=p^.w+l;
49                                    p:=p^.next;
50                               end;
51                    end;
52           end;
53 begin
54      readln(n,m);
55      for i:=1 to n do a[i]:=nil;
56      for i:=1 to m do
57          begin
58               readln(j,k,l);
59               add(j,k,l);
60          end;
61      dijkstra(1);
62      for i:=1 to n do
63          case c[i] of
64               1:writeln(1,' ---> ',i,' : ',b[i]);
65               0:writeln(1,' ---> ',i,' : ','Unavailable');
66          end;
67      readln;
68 end.

2.spfa单源最短路径模板

 1 type
 2         point=^node;
 3         node=record
 4                 g,w:longint;
 5                 next:point;
 6         end;
 7 var
 8         i,j,k,l,m,n:longint;
 9         a:array[0..100000] of point;
10         b,c:array[0..1000000] of longint;
11 procedure add(x,y,z:longint);inline;
12         var p:point;
13         begin
14                 new(p);p^.g:=y;p^.w:=z;
15                 p^.next:=a[x];a[x]:=p;
16         end;
17 procedure spfa(x:longint);inline;
18         var f,r:longint;p:point;
19         begin
20                 f:=1;r:=2;
21                 fillchar(c,sizeof(c),0);
22                 c[x]:=1;
23                 b[1]:=x;
24                 while f<r do
25                         begin
26                                 p:=a[b[f]];
27                                 while p<>nil do
28                                         begin
29                                                 if (c[p^.g]=0) or (c[p^.g]>(p^.w+c[b[f]])) then
30                                                         begin
31                                                                 c[p^.g]:=p^.w+c[b[f]];
32                                                                 b[r]:=p^.g;
33                                                                 inc(r);
34                                                         end;
35                                                 p:=p^.next;
36                                         end;
37                                 inc(f);
38                         end;
39                 for i:=1 to n do dec(c[i]);
40         end;
41 begin
42         readln(n,m);
43         for i:=1 to n do a[i]:=nil;
44         for i:=1 to m do
45                 begin
46                         readln(j,k);
47                         add(j,k,1);add(k,j,1);
48                 end;
49         spfa(1);
50         for i:=1 to n do
51                 case c[i] of
52                         -1:writeln(1,' ---> ',i,' : ','Unavailable');
53                         else writeln(1,' ---> ',i,' : ',c[i]);
54                 end;
55         readln; 
56 end.

3.bat对拍小程序

(PS:由于Bellman-Ford算法具有超高的时空浪费量,还有Floyd一般不用于单源最短路,所以只准备这些)

还有:这次采用的对拍模式如下——模拟一般OI赛制上的10组数据,30%数据满足规模为N<=10000 M<=100000;60%的数据满足规模为N<=30000 M<=200000;100%的数据满足N<=50000 M<=1000000。每10组这样的数据为一组,多组测试

公布结果——在30%的数据时,spfa用时200ms多点,dijkstra用时300ms多点

在60%数据时,spfa用时400ms多点,dijkstra用时1500-1800ms

在100%数据时,dpfa用时1300ms+,dijkstra用时11000-14000ms

差距就是——10倍,尤其是数量上去之后

原因——dijkstra里面最怕的就是一边接着一遍的扫描最小值,而且事实证明,如果像我原来预想的样子写堆优化的话——1.堆优化难写,因为不仅仅涉及到删除和加入新值 2.代码量会成倍的扩大。也就是说真正的成了O(N^2).而spfa是与边的密度相关的,且减少了许多的松弛操作

总结:事实的效果才能说明一切。更何况这个里面是随机生成的数据而不是OI的时候有意构造出来的更加强的数据。。。

(附:用于对拍的batch)

 1 @echo off
 2 :2
 3 set /a s=0
 4 cls
 5 :1
 6 set /a s=s+1
 7 echo Test %s%
 8 if %s% leq 3 (
 9 echo 10000 100000|fuckpath.exe >path.in
10 goto 4)
11 if %s% leq 6 (
12 echo 30000 200000|fuckpath.exe >path.in
13 goto 4)
14 if %s% leq 10 (
15 echo 50000 1000000|fuckpath.exe >path.in
16 goto 4)
17 :4
18 echo.|time
19 type path.in|spfa.exe >spfa.out
20 echo.|time
21 echo.|time
22 type path.in|dijkstra.exe >dijkstra.out
23 echo.|time
24 fc dijkstra.out spfa.out
25 if %s%==10 (goto 3)
26 goto 1
27 :3
28 pause
29 goto 2

 

上一篇: Magic Leap如何挑战微软?光纤投影仪 下一篇: 没有下一篇了!
发表评论
用户名: 匿名