2023年7月30日发(作者：)

（填坑）数学建模之旅⾏路线规划问题（状压+Dijkstra）最近突然想起很久以前同学问的⼀道数模题，是道NPC问题，当时不会搞，现在发现⽤状压可以搞出来，所以就把这个坑填上了设状态(S,u)表⽰已访问过的景点集合为S且当前在第u个景点，⽤求最短路的⽅式进⾏转移即可。虽然题⽬说每个景点可以经过多次，但最优路线还是每个景点都只经过了⼀次，囧...ps:原代码的Dijkstra算法有误，现已更正（spfa⽤惯了，Dijkstra都不会写了，唉）更新⽇期2019.1.5ps:上次更新的算法仍然有误，我以前图省事直接⽤d数组的值作为优先队列的权值，这样做是错误的（原因⾃⾏思考），但对于⼤多数情况求出来的答案还能够得到正解，因此曾导致我写错了很久都没有发现...（想写对Dijkstra不容易啊，溜了~~）更新⽇期2019.9.12#includeusing namespace std;typedef long long ll;const int INF=0x3f3f3f3f;const int N=10;int dis[N][N]= { {0,300,360,210,590,475,500,690}, {300,0,380,270,230,285,200,390}, {360,380,0,510,230,765,580,770}, {210,270,510,0,470,265,450,640}, {590,230,230,470,0,515,260,450}, {475,285,765,265,515,0,460,650}, {500,200,580,450,260,460,0,190}, {690,390,760,640,450,650,190,0},};int d[1< q;int Dij() { memset(d,INF,sizeof d); memset(vis,0,sizeof vis); ({1<<0,0,0}); d[1<<0][0]=0; while(!()) { int S=().S,u=().u,g=().g; (); if(g!=d[S][u])continue; if(u==7)continue; for(int v=1; v<8; ++v) { int S2=S|(1<